문제

골드바흐의 추측

풀이

골드바흐의 추측또한 소수로 판별하는 문제이기 때문에 10만까지의 정수의 소수를 구하면 된당 일단 소수가 아닌 것부터 걸러 내기 위해서 배열을 선언해본다

일단 10만까지의 소수는 루트 10만까지만 검증하면 소수들을 판별하면 된다. 루트 10만까지의 정수들이 서로 곱해지는경우 소수가 아니기때문에 전부 걸러주면 되는 것이다..

1. 소수 판별 배열 정의

boolean[] check = new boolean[100001];
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 2; i < Math.sqrt(100000); i++) {
	if (!check[i]) {
    	arr.add(i);
        // 소수가 아닌 것들을 걸러주겠다
        for (int i = i * i; i < 100000; i++) {
	    	check[i] = true;    
		}
    }
}

2. 골드바흐의 정의

Stringbuilder sb = new Stringbuilder();
int notFount = true;
while (true) {
	int n = sc.nextInt();
    if (n == 0) break;
    // 
    for (int i = 1; i < n / 2 + 1; i++) {
    	int p = arr.get(i);
    	if (!check[p] && check[n - p]) {
        	sb.append(n + " = " + p + " + " + (n - p));
            notFound = false;
            break;
        }
    }
}

여기에서 n / 2 + 1 까지 검증해주는 이유는 arr의 크기가 얼마나 되는지는 알수 없지만 n의 소수의 개수는 최대 n / 2 + 1 의 크기를 가지기 때문이다.
이부분이 좀 헷갈렸던것 같다.

정수론은 좀 많이 풀어봐야 한번에 느낌이올텐데... 물론 소수를 구하는데 있어서 배열을 사용하는 방법도 안쓰다보니 시간초과가 처음엔 나왔다. 어렵슴..

전체 코드

전체 코드