짝수 N
을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N
이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)
가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N
은 짝수이고, 2 < N ≤ 1,000,000
을 만족한다.
각각의 테스트 케이스마다 골드바흐 파티션의 수를 출력한다.
5
6
8
10
12
100
1
1
2
1
6
-문제를 만든 사람: baekjoon
-데이터를 추가한 사람: djm03178
-문제의 오타를 찾은 사람: jh05013
import java.io.*;
import java.util.ArrayList;
public class Code17103 {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int T=Integer.valueOf(br.readLine());
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
for(int i=0;i<T;i++){
int N=Integer.valueOf(br.readLine());
ArrayList<Boolean> prime=new ArrayList<>();
prime.add(false);//0
prime.add(false);//1
for(int j=2;j<=N;j++){
prime.add(j,true);
}
for(int j=2;(j*j)<=N;j++){
if(prime.get(j)){
for(int k=j*j;k<=N;k+=j){
prime.set(k,false);
}
}
}
int count=0;
for(int j=2;j<prime.size();j++){
if(prime.get(j)){
int remain=N-j;
if(remain<j){ //j는 5인데 remain이 3인 경우
continue;
}
else{
if(prime.get(remain)){
count++;
}
}
}
}
bw.write(String .valueOf(count)+"\n");
}
br.close();
bw.flush();
bw.close();
}
}
에라토스테네스 체를 이용했다!
범위 안의 소수들을 구해서, 만약 N-소수
해서 나머지도 소수로 true
로 되어있다면, 골드바흐의 파티션에 포함된다.
그리고 만약, (3,5) (5,3)은 같기 때문에 나머지가 지금 그 j
보다 작으면 탈락인것이다!