[알고리즘] 백준 17103 파이썬 - 골드바흐 파티션(에라토스테네스의 체)

 

17103번: 골드바흐 파티션

 

문제

• 골드바흐의 추측: 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다.

짝수 N을 두 소수의 합으로 나타내는 표현을 골드바흐 파티션이라고 한다. 짝수 N이 주어졌을 때, 골드바흐 파티션의 개수를 구해보자. 두 소수의 순서만 다른 것은 같은 파티션이다.

 

문제풀이

#소수가 저장되는 리스트
prime = []
n=1000000
#에라토스테네스의 체
arr = [False, False] + ([True] * (n - 1)) #01
for i in range(2, n+1):
    if arr[i]: #02
        prime.append(i)
        
    for j in range(i * 2, n, i): #03
        arr[j] = False
        
ans=[] #04
for i in range(int(input())):
	#05
    a = int(input())
    cnt=0
    #06
    for i in range(len(arr)):
        if prime[i]>a-prime[i]:
            break
        #07
        if arr[a-prime[i]]:
            cnt+=1
    #08
    ans.append(cnt)
print(*ans, sep='\n')

 - prime은 소수를 저장할 리스트이다.

- 에라토스테네스의 체를 이용하여 n까지의 소수를 prime에 저장할 것이다.

- #01 : n개의 리스트를 만들어준다. 기본적으로 소수만 True, 비소수이면 False로 저장할 것이다.

          초기값은 0,1을 제외한 2부터 n까지 모두 True로 저장을 한다.

- #02 : arr[i]가 소수인 경우 즉 True인 경우 prime에 값을 추가한다.

           애초에 시작값 2는 소수이기에 바로 prime에 값을 추가해도 상관이 없다.

- #03 : if문이 끝나고 시작값 2(i)부터 n까지 2(i)의 간격으로 for문을 돌린다.

           즉 2의 배수는 모두 소수가 아니므로, 모두 False로 값으로 바꿔준다.

           해당 for문을 그 다음에는 3, 4, 5 ... n까지 늘려가며 prime 값에 소수를 추가해준다.

 

- #04 : 사실상 여기서부터 문제의 시작이다. 값을 출력할 ans 리스트를 만들어준다.

- #05 : 테스트의 개수와 각 테스트 값을 적당히 입력받고, cnt 즉 개수를 저장할 변수를 선언한다.

- #06 : for문을 arr의 길이만큼 반복한다. 

           처음 if문을 해석하자면 "소수>입력받은 값-소수"이면 멈춘다는 뜻이다.

           즉 이 뜻은 골드바흐 파티션을 만족하기 위해서 "소수1+소수2=입력받은 값"을 이용하여,

           "소수>입력받은 값-소수"이면 조건을 성립하지 않는다는 것이다.

- #07 : 이 if문도 "소수=입력받은 값-소수"을 이용하여 arr[입력받은 값 - 소수] 값이 소수(True)라면

           해당 조건을 성립하기에 개수(cnt)에 1을 추가해준다.

- #08 : 입력받은 a의 조건을 성립하는 개수(cnt)를 ans에 추가해준다.

           최종적으로 그 개수를 \n을 기준으로 출력해준다.

 

 

에라토스테네스의 체 - 나무위키 (namu.wiki)