imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:09Z

New page

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

SummationOfFourPrimes/문보창 - Revision history

imported>Unknown at 05:28, 7 February 2021