BOJ 17103: 골드바흐 파티션 (Python)

문제

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

17103번: 골드바흐 파티션

 

 

코드

#에라토스테네스의 체
array = list[1000000]
a = [False, False] + [True]*(999999)

for i in range(2,1000000):
    if a[i]:
        for j in range(2*i, 1000000, i):
            a[j] = False

t = int(input())
for i in range(t):
    
    n = int(input())
    sum = 0
    
    x = n//2
    y = n//2
    
    if x%2==0:
        if a[x] and a[y]:
            if x+y == n:
                sum+=1
        x-=1
        y+=1
    while(x>1):
        if a[x] and a[y]:
            sum+=1
        x-=2
        y+=2
    print(sum)

 

 

풀이

이 문제는 에라토스테네스의 체를 사용하여 소수 판정을 해야 시간 초과가 뜨지 않는다.

 

에라토스테네스의 체

➡️ 말 그대로 체처럼 소수가 아닌 수들을 거르는 것이다.

1. 배열에 원하는 숫자까지 차례대로 숫자를 담는다. ex) 100까지의 소수를 구하고 싶다면 배열에 0,1,2,3,4,...,100을 담는다.
2. for문으로 0부터 100까지 돌면서 해당 숫자가 소수일 경우 이 숫자의 배수들은 모두 없애면 된다. 
3. 그러기 위해서는 0,1은 False로, 나머지 수들은 True로 초기화를 한다.
4. 0,1은 처음부터 False 이므로 for문 패스
5. 2부터 True 이므로 2의 배수들을 모두 없앤다. (False로 변경한다.)
6. 남는 것은 소수 뿐이다. 

 

골드바흐 파티션 구하는 법

N 이 20이라고 가정할 때 N을 2로 나눈 10을 기준으로 2씩 차이가 나는 순열을 만든다. 그러면 파란 선으로 이은 것과 같이 합이 N인 쌍이 구성된다. 여기서 나는 x를 중간값의 왼편인 3,5,7,9로, y를 중간값의 오른편인 11,13,15,17 로 두었다.

 

N/2 가 짝수이면 x는 N/2-1 로, y는 N/2+1 로 두고 시작한다.

 

Why?

짝수인 N/2 에서부터 2씩 차이가 나도록 숫자를 구성하면 모든 숫자가 짝수가 되는데 짝수는 2를 제외하고는 모두 소수가 아니므로  골드바흐 파티션의 조건에 부합하지 않기 때문이다.

⚠️ 그런데 이렇게 하면 N=4 일 때 x=2, y=2 처럼 쌍의 모든 수가 짝수이지만 모두 소수라서 골드바흐 파티션 조건에 부합하여도 무시되기 때문에 아래와 같이 따로 예외처리를 해주었다. 

    if x%2==0:
        if a[x] and a[y]: # N=4 일 때 (2,2) 는 골드바흐 파티션에 해당하므로 예외 처리를 해준다.
            if x+y == n:
                sum+=1
        x-=1
        y+=1

 

그리고 x가 1보다 작아지기 전까지 x는 2씩 줄이고, y는 2씩 늘리면서 x,y 가 모두 소수일 때 sum+=1 을 하여 골드바흐 파티션의 개수를 구하면 된다.

 

while(x>1):
        if a[x] and a[y]:
            sum+=1
        x-=2
        y+=2
    print(sum)

 

✅에라토스테네스의 체로 a라는 배열에 소수만을 True로 남겨두었으므로 위와 같은 if문이 가능하다.