소ê°� ¶
2005/02/18 Accepted 0:00.152 448
소수ì—� 대한 기본지ì‹�ì�´ 없어서 ìƒ�당히 ì• ë¥¼ 먹ì�€ ë¬¸ì œì�´ë‹¤. 2보다 í�° ì§�수는 모ë‘� ë‘� 소수ì�˜ 합으로 표현ë� 수 있다. ë¬¼ë¡ ì•„ì§�까진 가설ì�´ë‹¤. ìž…ë ¥ 천만기준ì—� 대해 8ì�´ìƒ�ì�˜ ëª¨ë“ ìˆ˜ëŠ” 소수 4ê°œì�˜ 합으로 표현ë� 수 있다는 ì „ì œì¡°ê±´ì�„ 세우니 ë¬¸ì œê°€ 한결 쉬워 보였다. 왜ëƒ�하면 소수 4ê°œì�˜ í•©ì�´ê¸° 때문ì—� 소수중 ìœ ì�¼í•œ ì§�수ì�¸ 2를 ì�´ìš©í•˜ë©´ 홀수 ë˜�한 소수ì�˜ 합으로 í‘œí˜„í• ìˆ˜ 있다. 8보다 ìž‘ì�€ 수를 ì œì™¸í•˜ê³¤ 모ë‘� 소수 4ê°œì�˜ 합으로 표현ë�˜ì–´ì§„다. ì‹¤ì œë¡œ. ì •ìˆ˜ë¡ ì—� 대해 í�¥ë¯¸ë¥¼ ëŠ�ë�¼ê²Œ í•´ 준 ë¬¸ì œì˜€ë‹¤.
소수ì—� 대한 기본지ì‹�ì�´ 없어서 ìƒ�당히 ì• ë¥¼ 먹ì�€ ë¬¸ì œì�´ë‹¤. 2보다 í�° ì§�수는 모ë‘� ë‘� 소수ì�˜ 합으로 표현ë� 수 있다. ë¬¼ë¡ ì•„ì§�까진 가설ì�´ë‹¤. ìž…ë ¥ 천만기준ì—� 대해 8ì�´ìƒ�ì�˜ ëª¨ë“ ìˆ˜ëŠ” 소수 4ê°œì�˜ 합으로 표현ë� 수 있다는 ì „ì œì¡°ê±´ì�„ 세우니 ë¬¸ì œê°€ 한결 쉬워 보였다. 왜ëƒ�하면 소수 4ê°œì�˜ í•©ì�´ê¸° 때문ì—� 소수중 ìœ ì�¼í•œ ì§�수ì�¸ 2를 ì�´ìš©í•˜ë©´ 홀수 ë˜�한 소수ì�˜ 합으로 í‘œí˜„í• ìˆ˜ 있다. 8보다 ìž‘ì�€ 수를 ì œì™¸í•˜ê³¤ 모ë‘� 소수 4ê°œì�˜ 합으로 표현ë�˜ì–´ì§„다. ì‹¤ì œë¡œ. ì •ìˆ˜ë¡ ì—� 대해 í�¥ë¯¸ë¥¼ ëŠ�ë�¼ê²Œ í•´ 준 ë¬¸ì œì˜€ë‹¤.
소스 ¶
~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;
}
}










