Summation Of Four Primes/곽세환

소감2 ¶

통과O
곰곰히 관찰해본 결과 소수 3개의 합으로 웬만한 수를 다 만들 수 있다는 것을 알았다.(모든 수를 만들수 있는지는 모르겠다) 그래서 일단 제일 큰 소수를 하나 구하고 나머지 값을 소수 3개의 합으로 나타내었다.
impossible과 Impossible. 은 다른거다.

소스2 ¶

~cpp 
//10168
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

#define PRIME_TABLE_SIZE 100

int primeTable[PRIME_TABLE_SIZE];
int primeCnt = 0;

void makePrimeTable()
{
	int i, j;
	primeTable[primeCnt++] = 2;
	for (i = 3; primeCnt < PRIME_TABLE_SIZE; i += 2)
	{
		for (j = 0; j < primeCnt; j++)
		{
			if (i % primeTable[j] == 0)
				break;
			else if (i / primeTable[j] <= primeTable[j])
			{
				primeTable[primeCnt++] = i;
				break;
			}
		}
	}
}

bool isPrime(int n)
{
	int i;
	if (n != 2 && n % 2 == 0)
		return false;
	for (i = 3; i <= sqrt(n); i += 2)
	{
		if (n % i == 0)
			return false;
	}
	return true;
}

int main()
{
	int input;
	int sumOfThreePrimes;
	int primes[4] = {0};
	int i, j, k;
	makePrimeTable();
	while (cin >> input)
	{
		primes[0] = primes[1] = primes[2] = primes[3] = 0;

	for (i = input - 6; i >= 2; i--)
	{
		if (isPrime(i))
		{
			primes[0] = i;
			sumOfThreePrimes = input - i;
			break;
		}
	}
	if (primes[0] == 0)
	{
		cout << "Impossible." << endl;
		continue;
	}

	for (i = 0; i < 100; i++)
		for (j = 0; j < 100; j++)
			for (k = 0; k < 100; k++)
			{
				if (sumOfThreePrimes == primeTable[i] + primeTable[j] + primeTable[k])
				{
					primes[1] = primeTable[i];
					primes[2] = primeTable[j];
					primes[3] = primeTable[k];
					i = j = k = 100;
				}
			}
	
	cout << primes[0] << " " << primes[1] << " " << primes[2] << " " << primes[3] << endl;
	}
	return 0;
}

[edit]

소감1 ¶

통과X
접근방법이 달라야한다. 내공이 아직 부족한것 같다.

[edit]

소스1 ¶

~cpp 
#include <iostream>
#include <cmath>
using namespace std;

bool is_prime(int n);
void sum_4prime(int n);

int prime[500000];
int prime_cnt = 0;

void main()
{
	int input;
	cin >> input;
	
	sum_4prime(input);
}

bool is_prime(int n)
{
	for (int i = 2; i <= sqrt(n); i++)
		if (n % i == 0)
			return false;
	return true;
}

void sum_4prime(int n)
{
	int i, j, k, l;
	for (i = 2; i <= n; i++)
	{
		if (is_prime(i))
		{
			prime[prime_cnt++] = i;
			//cout << i << endl;
		}
	}

	for (i = 0; i < prime_cnt; i++)
	{
		//if (prime[i] + prime[prime_cnt - 1] * 3 < n)
		//	continue;
		for (j = 0; j < prime_cnt; j++)
		{
			//if (prime[i] + prime[j] >= n)
			//	break;
			//if (prime[i] + prime[j] + prime[prime_cnt - 1] * 2 < n)
			//	continue;
				
			for (k = 0; k < prime_cnt; k++)
			{
				//if (prime[i] + prime[j] + prime[k] >= n)
				//	break;
				//if (prime[i] + prime[j] + prime[k] + prime[prime_cnt - 1] < n)
				//	continue;

				for (l = 0; l < prime_cnt; l++)
				{
					//if (prime[i] + prime[j] + prime[k] + prime[l] > n)
					//	break;
					if (prime[i] + prime[j] + prime[k] + prime[l] == n)
					{
						cout << prime[i] << " "	<< prime[j] << " " << prime[k] << " " << prime[l] << endl;
						return;
					}
				}
			}
		}
	}
	cout << "Impossible" << endl;
}

[edit]

댓글 ¶

SummationOfFourPrimes