1,000,000 이하의 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
ex) 8 = 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17, 42 = 5 + 37과 같이 나타낼 수 있다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
풀이
아,,, 머리 굳었는 지 이 문제 하나 이해 안돼서 2일 쏟은 거 같다. 이해가 안되니 집중도 풀리고 휴,,,,,,,
접근방법은 이러하다.
-
소수인지 판별하는 리스트(isPrime)를 하나 생성한다. (소수만을 담은 리스트를 추가 생성해서 풀이해도 된다. 나도 그렇게 처음 풀었다가 그냥 풀다보니 굳이? 필요 없겠는데 싶어서 소수만을 담은 리스트 생성은 하지 않았다.)
-
조건 중에 n을 홀수 소수의 합 형태로 만들 수 있는 조합이 여러 개인 경우, b-a가 가장 큰 것을 출력한다고 하였다. isPrime의 앞부분부터 뒤적뒤적 찾을 것이기 때문에 자연스레 a가 최소값이 될 것이고, 그에 따라 b-a 는 자연스레 최대값을 갖게 될 것이므로 따로 처리는 하지 않았다.
-
소수 a,b를 찾게 되면 isFind로 방법을 찾았음을 나타내고, 찾지 못하면 isFind의 값을 변경하여 "Goldbach's conjecture is wrong."를 출력하도록 하였다.
접근 방법은 위와 같고, 어디서 이해가 안갔냐,,,
아니 이거 sds 특강에서 다뤄주셨는데 다시 보니 이해가 안된다.
이해 안된 부분 1.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int n;
int N = 1000000;
boolean[] isPrime = new boolean[N + 1];
List<Integer> primeNums = new ArrayList<>();
for (int i = 2; i <= N; i++) { //★★★
if (!isPrime[i]) {
primeNums.add(i);
for (int j = i * i; j <= N; j += i) { //★★★
isPrime[j] = true;
}
}
}
System.out.println(primeNums);
}
}강의에서 본 코드 그대로 작성하였다.
실행시 발생한 에러는 인덱스 벗어났다는 에러.
아니 뭔 에러인지는 알지 나도,,,, 근데 왜 인덱스를 벗어나는 에러가 발생하는 건데......
그래서 찾은 에러 발생 이유.
첫번째 ★줄에서 i는 2~1,000,000까지 증가한다.
두번째 ★줄에서 이 i * i 연산을 한 값을 j에 저장하는데, 이때 j의 값이 int형의 범위를 벗어나게 된다. 그래서 오버플로우로 j의 값이 음수 값이 되는 거다. 쓰다보니 이해했네. 그러니까 자연스레 두번째 for문의 조건을 통과하게 된거고, isPrime[j] = true에 값을 저장하려니 j가 음수라 인덱스 outOfBoundsException이 발생하는 거구만
왜 헤맸냐면, j가 너무 커져서 isPrime이 outOfBoundsExcepiton나는 줄 알았다. 아니 너무 커졌으면 for문의 조건을 못통과하는게 맞는데?? 라는 생각도 함께 드니 어디서부터 잘못됐나 싶은거다....
이 부분은 질문해서 해결했고, 이제 해결 코드에서 이해가 안가는 부분
이해 안된 부분 2.
public class boj6588 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
boolean isFind;
int n;
int N = 1000000;
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i*i <= N; i++) { // i*i 를 하는 이유,
if (!isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = true;
}
}
} 왜 첫번째 for문에서 i * i 를 하는지가 이해가 안됐었다.
예를 들어, N이 10이라고 할 때, i * i를 조건으로 두면, i가 3일 때 종료되면서 5는 소수인지 아닌 지 체크 못하는 거 아냐? 5 이후의 숫자들은 어떻게 해? 라는 멍청한 생각에 오늘 꽤나 잠겨 있었다.
우리가 이 이중 for문을 통해 하려는 것은 2부터 N(1,000,000) 사이의 소수를 찾아내기 위해서이다.
i * i를 하는 이유는 다음과 같다.
N = 100 일때 갖는 순서쌍(a, b)은,
1, 100
2, 50
4, 25
5, 20
10, 10
20, 5
25, 4
50, 2
100, 110 이후에 순서쌍(a, b)은 10 이전에 찾았기 때문에 구할 필요가 없다.
10은 100의 제곱근이다. 우리는 N의 제곱근까지만 확인해보면 소수인지 아닌 지를 판단할 수 있다.
여기까지도 이해가 잘 안됐다. 아까 말했잖아 N = 10일 때, 다른 수들은 어떻게 해?
바로, 2번째 for문에서 i의 배수들을 처리해준다. 그러므로 isPrime[ ]에는 소수들만 false 값을 유지하고 있는 것이다.
N = 10 일 때, i * i <= N을 만족하는 i는 3까지 가능하다.
2는 소수이니 냅두고, 2의 배수들을 방문처리(isPrime[i] = true)
3도 소수이니 냅두고, 3의 배수들을 방문처리(isPrime[i] = true)
결과적으로 isPrime[i]에서 false를 갖는 i는 소수인 것이다.
위 코드로 소수를 확인하기 위한 배열이 생성된 것이다.
이제 입력받는 n에서 isPrime[ ]에 값을 뺀 값이 isPrime[ ]에 있는 지를 확인하면서 결과를 나타내면 된다.
package woohyeong;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class boj6588 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
boolean isFind;
int n;
int N = 1000000;
boolean[] isPrime = new boolean[N + 1];
for (int i = 2; i*i <= N; i++) { // i*i 를 하는 이유,
if (!isPrime[i]) {
for (int j = i * i; j <= N; j += i) {
isPrime[j] = true;
}
}
}
//System.out.println(primeNums);
while (true) {
isFind = false;
n = Integer.parseInt(br.readLine());
if (n == 0) {
break;
}
for (int i = 3; i < n; i++) {
if (!isPrime[i]) {
if (!isPrime[n - i]) {
sb.append(n + " = " + i + " + " + (n - i) + "\n");
isFind = true;
break;
}
}
}
if (!isFind) {
sb.append("Goldbach's conjecture is wrong.");
}
}
System.out.println(sb.toString());
}
}