백준 6588번 파이썬 문제풀이(수학 - 골드 바흐의 추측)

 

코드

import sys

questionRange = 1000000 #문제에서 주어진 n의 범위
array = [True] * (questionRange + 1) #소수를 저장할 리스트를 n의범위+1 만큼 선언 및 초기화
array[0], array[1] = False, False #0,1은 소수가 아니기에 False로 초기화

#에라토스테네스의체 공식으로 소수 구하기
for i in range(2, int(len(array) ** 0.5) + 1): #주어진범위의 제곱근까지만 돌기
    j = 2 # 각 인덱스 i에 곱할 j 선언
    while True:
        if array[i]: #만약 리스트의 인덱스가 True라면(소수라면)
            array[i * j] = False #그의 배수들은 모두 소수가 아니게 된다.
            j += 1 #j값 증가
            if i * j >= len(array): #만약 j가 계속해서 증가하다가 배열의 길이보다 같거나 커진다면
                break #반복문 탈출
        else: #만약 리스트의 인덱스가 False라면(소수가 아니라면) <- 소수가 아니라는 소리는 이미 앞에서 해당 배수를 다 False로 처리했기 때문에
            break #반복문 탈출

while True: #무한반복
    n = int(sys.stdin.readline()) #n을 입력받는다.
    if n == 0: break #만약 n이 0라면 반복문탈출
    resultA, resultB = 0, (questionRange + 1) #초기 reusltA,resultB의 값에다 A는 0 B는 문제에서 주어진 범위보다 큰 값을 대입
    a = 0 #a를 0으로 초기화
    b = n #b를 0을 초기화
    while True:
        if array[a] and array[b]: #만약 a,b가 모두 소수라면
            resultA = a #그 값을 resultA값에 대입
            resultB = b #그 값을 resultB값에 대입
            break #반복문 탈출
        a += 1 #소수가 아니라면 a는 1씩증가
        b -= 1 #b는 1씩 감소
    if resultA != 0 and resultB != (questionRange + 1): #resultA,resultB의 값이 초기값과 다르다면
        print(f'{n} = {resultA} + {resultB}') #그 값을 출력
    else: #초기값과 같다면
        print("Goldbach's conjecture is wrong.")

 

-> 이 문제는 https://ji-gwang.tistory.com/219 하고 거의 동일한 문제이다. 차이점은 앞선 문제에서는 두 소수a,b의 값의 차가 가장 작은 a,b를 찾아야 한다면 이번에는 두 소수 a,b의 값의 차가 가장 큰 a,b를 찾아야 한다는 것이다. 

 

이 문제는 이 법칙만 알면 풀 수 있다. 짝수 n 을 절반으로 나눴을 경우 a는 +1 씩 b는 -1씩 할 경우 같은 위치에 있는 두소수의 덧셈의 값이 항상 n을 성립한다는 것이다. 예를 들어  20 을 2로 나눈 10을 +1,-1씩 해보면 (9,11) , (8,12) , (7,13) ... 이런식으로나오는데 (7,13) 이 둘다 소수이고 (3,17) 이 또한 둘다 소수이다.

 

위 문제를 풀기 위해선 이를 응용하기만 하면 된다. 반대로 a,b 를 0하고 n 부터 하나는 +1 씩 하나는 -1씩 계산해 나가면 된다. 똑같이 n=20이라고 할 때 a =0 , b =20 을 설정하고 (1,19),(2,18),(3,17)... 이런식으로 값이 등장하게 되는데 여기서 (3,17)이 가장 차가 큰 두 소수가 되기 때문에 이값을 찾은 후 반복문을 탈출하면 되는 식으로 문제를 풀면 된다.