합이 C++에서 주어진 N과 같은 최대 소수

이 문제에서는 숫자 n이 주어집니다. 우리의 임무는 합이 주어진 N과 같은 소수의 최대 개수를 찾는 것입니다.

여기에서 더할 때 그 수와 같을 소수의 최대 수를 찾습니다.

소수는 자기 자신이나 1로 나눌 수 있는 수입니다.

문제를 이해하기 위해 예를 들어 보겠습니다 -

입력 - 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이 홀수이면 합계의 모든 소수는 3이 되는 소수를 제외하고 2가 됩니다. 따라서 개수는 (n-1/2)가 됩니다.

예시

C++에서 주어진 N과 합이 같은 최대 소수를 찾는 프로그램

#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