Số nguyên tố tối đa có tổng bằng N đã cho trong C ++

Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ của chúng ta là tìm số lượng lớn nhất các số nguyên tố có tổng bằng N.

Ở đây, chúng ta sẽ tìm thấy số lượng các số nguyên tố lớn nhất mà khi thêm vào sẽ bằng một số.

Số nguyên tố là những số có thể chia hết cho chính chúng hoặc một.

hãy lấy một ví dụ để hiểu vấn đề -

Đầu vào - N =9

Đầu ra - 4

Giải thích -

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.

Số lượng các số nguyên tố lớn nhất được sử dụng sẽ dựa trên số lượng các số nguyên tố nhỏ nhất có thể được thêm vào để tạo thành tổng.

Vì vậy, số nguyên tố nhỏ nhất là 2. Và số nguyên tố lớn hơn liên tiếp là 3, là số lẻ.

Vì vậy, số lượng sẽ được tối đa hóa nếu chúng tôi chỉ sử dụng 2 và 3 trong khi tính tổng. Dựa trên điều này, chúng ta có thể phân chia vấn đề trong hai trường hợp -

Trường hợp 1 - nếu N chẵn, tất cả các số nguyên tố trong tổng sẽ là 2’s. Vì vậy, số lượng sẽ là n / 2.

Trường hợp 2 - nếu N là số lẻ, tất cả các số nguyên tố trong tổng sẽ là 2 trừ một số sẽ là 3. Vì vậy, số đếm sẽ là (n-1/2).

Ví dụ

Chương trình tìm Số nguyên tố tối đa có tổng bằng N cho trước trong 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;
}

Đầu ra

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