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

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

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

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน -

ป้อนข้อมูล − N =9

ผลผลิต − 4

คำอธิบาย −

9 can be repressed as the sum of prime numbers in the following ways:
2, 2, 2, 3
3, 3, 3
2, 2, 5
2, 7
Out of these the maximum number of primes used is 4.

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

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

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

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

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

ตัวอย่าง

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

#include <iostream>
using namespace std;
int maxPrimeCount(int n){
   //For odd case the result will same as (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