boj)17103 - 골드바흐 파티션
2020. 9. 16. 16:10ㆍPS/boj
import java.io.*;
// # 골드바흐 파티션
public class boj_17103 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
static boolean[] prime = new boolean[1000001];
static int ans;
public static void main(String[] args) throws IOException {
// 1. 1,000,001 이하의 소수 담기
for (int i = 2; i < prime.length; i++) {
prime[i] = true;
}
for (int i = 2; i*i < prime.length; i++) {
for (int j = i*2; j < prime.length; j+=i) {
prime[j] = false;
}
}
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
for (int j = 2; j <= n/2; j++) {
if (prime[j] && prime[n-j]) {
ans++;
}
}
bw.write(ans + "\n");
ans = 0;
}
bw.flush();
bw.close();
}
}
- 바보같이 for문 한번 끝날때마다 ans를 깜빡하고 초기화 안시킴 ...
- 에라토스테네스의 체 로 주어진 범위 안의 소수들을 배열에 담기
- n=a+b를 만족하는 소수 a,b를 prime에서 검사하고 맞다면 ++
- 근데 for문의 범위를 n까지 돌면 중복이 있으니 j <= n/2; 까지만 돌아준다 .
'PS > boj' 카테고리의 다른 글
boj)11726 - 2xn 타일링 (0) | 2020.09.16 |
---|---|
boj)1463 - 1로 만들기 (0) | 2020.09.16 |
boj)1212 - 8진수 2진수 (0) | 2020.09.16 |
boj)1373 - 2진수 8진수 (0) | 2020.09.16 |
boj)17087 - 숨바꼭질 6 (0) | 2020.09.15 |