문제
- 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.
짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
입력
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
출력
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.
예제 입력 1
5 6 8 10 12 100 |
예제 출력 1
1 1 2 1 6 |
더보기
Solution
#include<stdio.h>
#include<stdbool.h>
int main(void)
{
int T;
bool sieve[1000001]={false, };
for(int i=3;i<1000001;i+=2)
sieve[i]=true;
for(int i=3;i<1000001;i+=2)
if(sieve[i])
for(int j=2*i;j<1000001;j+=i)
sieve[j]=false;
scanf("%d", &T);
for(int t=0;t<T;t++)
{
int N, count=0;
scanf("%d", &N);
for(int i=3;i*2<=N;i+=2)
count+=sieve[i]&&sieve[N-i];
printf("%d\n", N==4?1:count);
}
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 11104번: Fridge of Your Dreams (0) | 2020.11.28 |
---|---|
<백준 알고리즘> 14568번: 2017 연세대학교 프로그래밍 경시대회 (0) | 2020.11.28 |
<백준 알고리즘> 12756번: 고급 여관 (0) | 2020.11.28 |
<백준 알고리즘> 15965번: K번째 소수 (0) | 2020.11.28 |
<백준 알고리즘> 13866번: 팀 나누기 (0) | 2020.11.28 |