[BOJ_6588] 골드바흐의 추측

문제

1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.

4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.

예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.

이 추측은 아직도 해결되지 않은 문제이다.

백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.

입력

입력은 하나 또는 그 이상의 테스트 케이스로 이루어져 있다. 테스트 케이스의 개수는 100,000개를 넘지 않는다.

각 테스트 케이스는 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력한다. 또, 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

예제 입력 1 복사

8
20
42
0

예제 출력 1 복사

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

풀면서 느낀점

사실 골드바흐의 추측은 저번 스터디 시간에 풀었는데 당시에 시간초과에 늪에 빠져서 고생했던 기억이 있었다. 그당시에는 에라토스테네스의 체의 알고리즘을 사용하지 않고, 시간을 갈아가면서 어떻게든 시간을 줄여보려고 고생했는데 그당시의 코드를 바라보면 무지성에서 N//2 만큼 돌면 조금은 줄지 않을까라는 생각에 코드를 짰는데 결론적으로 시간초과가 났었다.

import sys
input = sys.stdin.readline
# sys.stdin = open('input.txt')

T = int(input())
for _ in range(1,T+1):

    N = int(input())
    result = [] 

    for i in range(1,N//2+1,2):

        min_num,max_num = i, N-i

        min_count = 0
        idx = 3 

        while idx <= min_num:

            if min_num %idx ==0:
                min_count +=1
            idx += 2
 
        max_count = 0
        idx = 3  

        while idx <= max_num:
            if max_num % idx ==0:
                max_count +=1
            idx += 2


        if min_count ==1 and max_count ==1:
            result= [min_num,max_num]


    print(*result)

그 다음으로 시도한것은 특정 숫자가 소수인지 판별하는 함수가 제곱근만큼만 돌고 있어서 겨우겨우겨우 시간초과를 면했다.

import sys
import math
input = sys.stdin.readline
# sys.stdin = open('input.txt')

T = int(input())


def is_prime_number(x):
    for j in range(2, int(math.sqrt(x)) + 1):
        if x % j == 0:
            return False
    return True


for tc in range(1, T + 1):
    N = int(input())
    result = []
    for i in range(N // 2, 1, -1):

        if is_prime_number(i) and is_prime_number(N - i):
            result.append([i,N-i, (N-i-i)])

    result.sort(key= lambda x:x[2])
    print(result[0][0],result[0][1])

나의 코드

에라토스테네스의 체 알고리즘 알아보기

그전에 스터디를 통해서 에라토스테네스의 체의 개념을 배웠고, 다시 풀어볼 기회가 생겨 로직을 구현해보았다.

생각보단 알고리즘 자체가 쉽고 좋아서 이해하고 나니까 빠르게 로직을 구현할 수 있었다.

# M, N = map(int, input().split())
last_num = 1000000
temp = [i for i in range(last_num + 1)]

for i in range(2, int(len(temp) ** 0.5) + 1):
    if temp[i] != 0:
        cnt = 2
        while True:
            if temp[i] * cnt > last_num:
                break
            else:
                temp[temp[i] * cnt] = 0
                cnt += 1
temp[1] = 0


while True:
    nums = int(input())
    if not nums:
        break

    for i in range(nums - 1, nums // 2 - 1, -1):
        if temp[i] and temp[nums - temp[i]]:
            print("{} = {} + {}".format(nums, temp[nums - temp[i]], temp[i]))
            break
    else:
        print("Goldbach's conjecture is wrong.")