백준 - 9020번

골드바흐의 추측

https://www.acmicpc.net/problem/9020

9020번: 골드바흐의 추측

에라토스테네스의 체 방법으로 10000까지의 수들 중 소수를 먼저 구하고 시작했다.

max = 10000
numbers = [ True for _ in range(max)]
for i in range(2, max):
    if numbers[i]:
        for j in range(2*i, max, i):
            numbers[j] = False
T = int(input())
for k in range(T):
    N = int(input())
    for i in range(int(N/2), 0, -1):
        if numbers[i]:
            if numbers[N-i]:
                print(i, N-i)
                break

1) ~ 6) 10000까지의 소수를 구함

7) ~ 8) 몇 번 반복할 것인지 정함

9) 골드바흐 파티션을 찾을 수 입력받음(N)

10) i를 N/2부터 1씩 감소시키며 반복문 실행(N이 짝수라고 했기 때문에 int는 안써도 될듯)

11) numbers[i]를 통해 i 가 소수인지 확인함

12) i가 소수이면 N-i도 소수인지 확인

13) 둘 다 소수이면 두 수를 출력하고, 반복문을 마친다.

 

N/2부터 탐색하기 시작한 이유는 두 소수의 차이가 가장 작은 경우를 출력해야 하기 때문이다. 어떤 수가 두 수의 합으로 나눠진다면, 두 수가 N/2에 가까울수록 차이가 적어진다.

 

입력값이 4보다 같거나 큰 짝수라고 명시되어있고, 2보다 큰 모든 짝수는 골드바흐 파티션을 가진다고 했기 때문에 예외에 대한 처리는 하지 않았다.

 

 

*변수를 감소시키는 반복문

자주 사용하는 반복문은 for i in range(a, b)이다. 보통 세 번째 변수를 적지 않으면 a부터 1씩 증가해 b-1까지의 수를 사용한다.

세 번째 변수를 사용한다면(range(a, b, c)) a부터 c만큼 증가해 b-1까지의 수를 사용한다.

변수를 감소시키려면 c를 음수로 적어두면 된다.

10) for i in range(int(N/2), 0, -1):

의 경우 i는 N/2, (N/2 - 1), (N/2 - 2) ... 2, 1, 0까지 사용하게 된다. -1이 아닌 다른 음수를 사용해 -c만큼씩 줄어드는 배열을 사용할 수도 있다.