Summation Of Four Primes/문보창

소감 ¶

2005/02/18 Accepted 0:00.152 448
소수에 대한 기본지식이 없어서 상당히 애를 먹은 문제이다. 2보다 큰 짝수는 모두 두 소수의 합으로 표현될 수 있다. 물론 아직까진 가설이다. 입력 천만기준에 대해 8이상의 모든 수는 소수 4개의 합으로 표현될 수 있다는 전제조건을 세우니 문제가 한결 쉬워 보였다. 왜냐하면 소수 4개의 합이기 때문에 소수중 유일한 짝수인 2를 이용하면 홀수 또한 소수의 합으로 표현할 수 있다. 8보다 작은 수를 제외하곤 모두 소수 4개의 합으로 표현되어진다. 실제로. 정수론에 대해 흥미를 느끼게 해 준 문제였다.

[edit]

소스 ¶

~cpp 
// no10168 - SumOfFourPrimes(a)  
#include <iostream>      
#include <cmath>      
using namespace std;      
 
const int MAX = 450;   
 
void setPrimeArr(int * prim);      
bool findPrim(int formerPrim, bool isEven, int * prim);      
void showPrime(int prime1, int prime2, bool isEven);   
 
int main()      
{      
    int number;   
    int primes[MAX] = {2, 3, 5, 7, 11, 13,};      
    setPrimeArr(primes);     
    while (cin >> number)  
    {  
        if (number < 8)      
             cout << "Impossible.";  
        else if (number % 2 != 0) 
        { 
             cout << "2 3 ";      
             findPrim(number - 5, false, primes);  
        } 
        else if (number % 4 == 0)                                                            
             findPrim(number/2, true, primes);   
        else  
        {  
             findPrim(number/2 - 1, false, primes); 
             findPrim(number/2 + 1, false, primes);      
        }      
        cout << endl;      
    }  
    return 0;      
}   
 
bool findPrim(int formerPrim, bool isEven, int * prim)      
{ 
    bool success; 
    int prime1, prime2;                                                  
    for (int i=0; i < MAX; i++)      
    {      
        prime1 = prim[i];      
        prime2 = formerPrim - prime1;   
        success = true; 
        for (int j=0; j < MAX; j++)      
        {      
             if(prime2 > prim[j] && prime2 % prim[j] == 0)      
	     { 
                  success = false;; 
                  break;      
	     } 
        }      
        if (success)      
        {      
             showPrime(prime1, prime2, isEven);      
             break;      
        }      
    }      
    return true;      
}  
 
void showPrime(int prime1, int prime2, bool isEven)  
{  
    cout << prime1 << " " << prime2 << " ";      
    if (isEven)      
        cout << prime1 << " " << prime2;      
}     
 
void setPrimeArr(int * prim)      
{      
    int countPrimes = 6;      
    bool boolPrimes;      
    for (int i=15; ; i+=2)      
    {            
        boolPrimes = true;      
        for (int j=3; j <= sqrt(i); j+=2)      
        {      
            if (i % j == 0)      
            {      
                boolPrimes = false;      
                break;      
            }      
        }      
        if(boolPrimes)      
            prim[countPrimes++] = i;   
        if (countPrimes > MAX) 
            break; 
   }      
}

----
SummationOfFourPrimes 문보창