[BOJ][python] 6588. 골드바흐의 추측

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

6588번: 골드바흐의 추측

---

💡IDEA

수학을 사용하는 문제이다.

문제는 크게 어렵지 않지만 시간초과의 늪에 빠지기 쉬운 문제이다.

소수를 구해두는 건 while문 안에 넣으면 시간이 오래 걸리므로 먼저 계산해두어야 한다.

구해둔 이 소수배열을 앞에서부터 확인하는데, 더해서 n이 되는 소수를 구해야 하므로 i번째가 소수인 것과 n-i번째가 소수인 것을 확인해주면 된다. 발견할 시엔 출력 양식에 맞추어서 출력해준다.

 

📌CODE

prime = [1] * (1000000 + 1)
prime[0] = 0
prime[1] = 0
m = int(1000000 ** 0.5)
for i in range(2, m + 1):
    if prime[i]:
        for j in range(2 * i, 1000000 + 1, i):
            prime[j] = 0

while True:
    n = int(input())
    if n == 0:
        break

    for i in range(2, 1000000+1):
        if prime[i] and prime[n-i]:
            print("{} = {} + {}".format(n, i, n-i))
            break