[ 2023-05-30 🪱 TIL ]

백준 6588번

import sys

input = sys.stdin.readline

sosu = [False, False] + [True] * 1000000
# index를 가지고 소수를 판단

for i in range(2, 1000):
    if sosu[i]:
        for j in range(i * 2, 1000000, i):
            sosu[j] = False
# 에라토스테네스의 체를 사용하여 해당 인덱스의 값인 자연수가 
# 소수인 것들을 True로 설정 

while True:
    n = int(input())
    half_n = n // 2
    check = True
    if n < 6:
        break
    for a in range(3, half_n + 1, 2):
    	# 동시에 a와 n-a 2개를 확인하기에 n의 반 값으로 for문을 돌릴 수 있다.
        if sosu[a] and sosu[n - a]:
            print("{} = {} + {}".format(n, a, (n-a)))
            check = False
            break
    if check:
        print("Goldbach's conjecture is wrong.")

소수 문제가 나오면 항상 제곱근을 사용하여 체크하는 방법을 고집해왔습니다.
하지만 이 문제에서 그 풀이로 문제를 풀면 시간 초과가 발생하는 것을 확인하였습니다...ㅠ

그래서 찾아보았더니 에라토스테네스의 체를 사용한 풀이를 알게되었습니다.
에라토스테네스의 체의 시간복잡도는 O(n * log(log n)) 입니다.