[Python] 백준 17103번 (골드바흐 파티션) [실버2]

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

N의 범위가 1000000까지 이므로 에라토스테네스의 체를 사용하면 될 것 같다.

 

정답

import sys

prime_list = [True for _ in range(1000001)]

prime_list[0] = False
prime_list[1] = False

for i in range(2, 1000001):
    if prime_list[i] == True:
        for j in range(i*2, 1000001, i):
            prime_list[j] = False

prime_num = []
for i in range(len(prime_list)):
    if prime_list[i] == True:
        prime_num.append(i)

T = int(sys.stdin.readline())

for i in range(T):
    num = int(sys.stdin.readline())
    count = 0

    for prime in prime_num:
        if prime > num/2:
            break
        if prime_list[num - prime] == True:
            count += 1
    
    sys.stdout.write(str(count) + '\n')

 

풀이

1. prime_list를 통해 0부터 1000000번 인덱스까지 모두 True로 채워준다.

prime_list = [True for _ in range(1000001)]

 

2. 숫자 0과 1은 소수가 아니므로 False를 준다.

prime_list[0] = False
prime_list[1] = False

 

3. 숫자 2부터는 에라토스테네스의 체를 통해 소수를 판정한다.

for i in range(2, 1000001): # 2부터 1000000까지 탐색
    if prime_list[i] == True: # 만약 숫자 i가 소수이면
        for j in range(i*2, 1000001, i):
            prime_list[j] = False # i의 배수들은 모두 False로

 

4. prime_list에서 True인 인덱스만 prime_num에 추가한다. (2부터 1000000까지의 소수 리스트)

prime_num = []
for i in range(len(prime_list)):
    if prime_list[i] == True: # i가 소수이면
        prime_num.append(i) # prime_num에 추가

 

5. prime값은 무조건 소수이므로 num - prime값도 소수이면 count 증가

for i in range(T):
    num = int(sys.stdin.readline())
    count = 0

    for prime in prime_num:
        if prime > num/2:
            break
        if prime_list[num - prime] == True:
            count += 1
    
    sys.stdout.write(str(count) + '\n')