จำนวนจำนวนเฉพาะสูงสุดที่ผลรวมเท่ากับ N ใน C++

บทนำ

ในปัญหานี้ เราได้รับตัวเลข n มา ภารกิจคือหาจำนวนสูงสุดของจำนวนเฉพาะที่ผลรวมเท่ากับ N ที่กำหนด

เราจะหาจำนวนสูงสุดของจำนวนเฉพาะที่เมื่อรวมกันจะเท่ากับตัวเลขนั้น

จำนวนเฉพาะคือจำนวนที่หารลงตัวได้ด้วยตัวมันเองหรือ 1 เท่านั้น

ตัวอย่าง

อินพุต - N = 9

เอาต์พุต - 4

คำอธิบาย -

9 สามารถแทนเป็นผลรวมของจำนวนเฉพาะได้ดังนี้:
2, 2, 2, 3
3, 3, 3
2, 2, 5
2, 7
จากทั้งหมด จำนวนเฉพาะสูงสุดที่ใช้คือ 4

จำนวนเฉพาะสูงสุดที่ใช้จะขึ้นอยู่กับว่าสามารถบวกจำนวนเฉพาะที่เล็กที่สุดได้กี่ตัวเพื่อให้ได้ผลรวม

จำนวนเฉพาะที่เล็กที่สุดคือ 2 และจำนวนเฉพาะถัดไปคือ 3 ซึ่งเป็นเลขคี่

ดังนั้น จำนวนจะสูงสุดถ้าเราใช้แค่ 2 และ 3 ในการคำนวณผลรวม จากนี้เราสามารถแบ่งปัญหาเป็น 2 กรณี -

กรณี 1 - ถ้า N เป็นเลขคู่ จำนวนเฉพาะในผลรวมจะเป็น 2 ทั้งหมด ดังนั้นจำนวนคือ n/2

กรณี 2 - ถ้า N เป็นเลขคี่ จำนวนเฉพาะในผลรวมจะเป็น 2 ทั้งหมด ยกเว้น 1 ตัวที่จะเป็น 3 ดังนั้นจำนวนคือ (n-1)/2

ตัวอย่างโปรแกรม

#include <iostream>
using namespace std;

int maxPrimeCount(int n) {
    // สำหรับกรณีคี่ ผลลัพธ์จะเหมือนกับ (n-1)/2
    return n / 2;
}

int main() {
    int n = 9;
    cout << "The maximum number of primes whose sum is equal to " << n << " is " << maxPrimeCount(n);
    return 0;
}

ผลลัพธ์

The maximum number of primes whose sum is equal to 9 is 4

คำอธิบาย

การหารจำนวนเต็ม (Integer Division) ใน C++ จะตัดทศนิยมทิ้ง ดังนั้น n/2 ให้คำตอบที่ถูกต้องทั้งกรณีคู่และคี่:

• N=9 (คี่): 9/2 = 4 (เหมือน (9-1)/2 = 4)
• N=10 (คู่): 10/2 = 5