[백준 9020][파이썬] 골드바흐의 추측 소수 판별 (에라토스테네스의 체)

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

9020번: 골드바흐의 추측

알고리즘 문제에서 소수 판별을 할 때 사용하는 알고리즘은 일반적으로 두 종류가 있다.

 

반복문으로 나누어 떨어지는 수가 없는지 확인하는 방법과

 

에라토스테네스의 체를 사용하는 방법이 있다.

https://blog.naver.com/growth_s/222745036373

[알고리즘] 소수 판별 알고리즘

 

이 문제에서는 파이썬으로 에라토스테네스의 체를 구현해보려한다.

 

1부터 10000까지 소수를 판별해야한다면 길이가 10001이고 모든 값이 True인 리스트를 만든다.

 

그리고 인덱스를 2부터 하나씩 증가해가며 배수에 해당하는 인덱스의 값을 False로 바꾼다.

 

prime = [True]*10001
prime[0:2]=[False,False]
for i in range(2, 10001):
    for j in range(i+i, 10001, i):
        prime[j]=False

이제 n이 소수인지 알고 싶다면 prime[n]의 값을 보면 된다.

 

prime[n]이 True라면 소수이고 False라면 소수가 아니다.

 

본격적으로 문제를 풀어보자면 특정 정수의 값을 두 소수의 합으로 표현해야한다.

 

이 경우의 수는 여러가지가 나올 수 있는데 그럴 경우 두 소수의 차이가 가장 작은 것을 선택한다.

 

무조건 짝수가 입력값으로 들어오니까 들어온 값을 2로 나눈 값부터 시작한다.

 

그리고 차이를 점점 벌려나가면서 가장 먼저 소수 두 개가 나오는 값이 곧 정답이 된다.

 

<전체 코드>

prime = [True]*10001
prime[0:2]=[False,False]
for i in range(2, 10001):
    for j in range(i+i, 10001, i):
        prime[j]=False
t=int(input())
for _ in range(t):
    n=int(input())
    for i in range(n//2, 10000):
        if prime[n-i] and prime[i]: #둘 다 소수라면
            print(n-i, i)
            break