문제
정수론(수학)에서, 세 개의 소수 문제(3-primes problem) 는 다음과 같은 추측을 말한다.
'5보다 큰 임의의 홀수는 정확히 세 개의 소수들의 합으로 나타낼 수 있다. 물론 하나의 소수를 여러 번 더할 수도 있다.'
예를 들면,
- 7 = 2 + 2 + 3
- 11 = 2 + 2 + 7
- 25 = 7 + 7 + 11
5보다 큰 임의의 홀수를 입력받아서, 그 홀수가 어떻게 세 소수의 합으로 표현될 수 있는지 (또는 불가능한지) 알아보는 프로그램을 작성하시오.
입력
첫째 줄에 T(Test Case의 수를 의미함)가 주어진다.
입력은 T개의 Test Case로 이루어진다.
각 Test Case는 하나의 정수 K (7 ≤ K < 1,000, K는 홀수)로 구성된다.
출력
T줄에 걸쳐서, 각 줄에 K가 어떻게 세 소수의 합으로 표현되는지 출력해야 한다.
가능하다면 그 세 소수를 오름차순 정렬하여 출력하면 된다.
여러 개의 답이 가능하다면 그 중 하나만 출력하면 되고, 만약 불가능하다면 0을 출력한다.
예제 입력 1
3 7 11 25 |
예제 출력 1
2 2 3 2 2 7 5 7 13 |
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
bool isPrime(int N)
{
if(N<2)
return false;
else if(N==2)
return true;
else if(N%2==0)
return false;
else
for(int n=3;n*n<=N;n+=2)
if(N%n==0)
return false;
return true;
}
int main(void)
{
int count=1, prime[167], T, K;
prime[0]=2;
for(int i=3;i<997;i+=2)
if(isPrime(i))
prime[count++]=i;
scanf("%d", &T);
for(int t=0;t<T;t++)
{
bool solved=false;
scanf("%d", &K);
for(int i=0;prime[i]<K;i++)
{
for(int j=i;prime[i]+prime[j]<K;j++)
{
for(int k=j;prime[i]+prime[j]+prime[k]<=K;k++)
if(prime[i]+prime[j]+prime[k]==K)
{
solved=true;
printf("%d %d %d\n", prime[i], prime[j], prime[k]);
}
if(solved)
break;
}
if(solved)
break;
}
if(!solved)
printf("0\n");
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 2986번: 파스칼 (0) | 2020.12.26 |
---|---|
<백준 알고리즘> 1731번: 추론 (0) | 2020.12.26 |
<백준 알고리즘> 15992번: 1, 2, 3 더하기 7 (0) | 2020.12.24 |
<백준 알고리즘> 15990번: 1, 2, 3 더하기 5 (0) | 2020.12.23 |
<백준 알고리즘> 15988번: 1, 2, 3 더하기 3 (0) | 2020.12.23 |