Problem Solving/Java
백준 17103 골드바흐 파티션 문제풀이 ( Java )
TakeKnowledge
2019. 10. 22. 21:58
반응형
17103번: 골드바흐 파티션
첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 짝수이고, 2 < N ≤ 1,000,000을 만족한다.
www.acmicpc.net
골드 바흐의 추측과 비슷한 문제다. ( 골드바흐의 추측 풀이는 아래에서 )
백준 6588번 골드바흐의 추측 에라토스 테네스의 체 활용 문제풀이 ( Java )
6588번: 골드바흐의 추측 문제 1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다. 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼..
takeknowledge.tistory.com
다만 여기서는 가능한 조합의 갯수를 출력해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
public class Main {
public static final int MAX = 1000000;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
// reader writer 생성
boolean[] isNotPrime = new boolean[MAX + 1];
// 소수 판별 배열 선언
isNotPrime[0] = true;
isNotPrime[1] = true;
// 0과 1 제외
for (int i = 2; i < MAX; i++) {
if (isNotPrime[i] == false) {
// 소수 찾으면
for (int j = i + i; j <= MAX; j += i) {
isNotPrime[j] = true;
// 그 배수들 소수가 아니라 표시
}
}
}
// MAX까지 소수 판별
int n = Integer.parseInt(br.readLine());
// 입력 받을 갯수
for (int i = 0; i < n; i++) {
// 입력 받은 만큼 돈다
int count = 0;
int m = Integer.parseInt(br.readLine());
// 확인할 수 입력 받아서
for (int j = 3; j < m; j++) {
// 표시된 소수 배열 3부터 돌면서
if (isNotPrime[j] == false && j >= m-j) {
// 소수 찾고 j 가 m-j보다 클 경우만이라는 조건을 달아 중복을 방지한 다음
if (isNotPrime[m - j] == false) {
count++;
// 카운트 올린다
}
}
}
bw.write('\n');
}
}
}
|
이렇게 구하면 되는데 핵심은 j >= m - j 로 중복을 방지하는 부분이다
저 조건없이 예를 들어 합해서 8을 만들 수 있는 두 소수를 구하면 3과 5, 5와 3 모두 카운트 되서 2가 나온다
그러나 위와 같이 조건을 걸면 j가 3일 경우는 체크가 되지 않기 때문에 정확한 답이 나온다
반응형