https://www.acmicpc.net/problem/6588
시간 1초, 메모리 256MB
input :
- 짝수 정수 n 하나로 이루어져 있다. (6 ≤ n ≤ 1000000)
- 마지막 줄에는 0이 하나 주어진다.
output :
- n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수
- n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 것을 출력
- n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력
괜히 defaultdict 쓰다가 시간 복잡도만 말아먹고 다시 리스트를 이용했다.. 매우 빠르군
그래도 합성수 (곱셈으로 n을 만드려 할 때) 제곱근을 이용해서 소수를 판별할 수 있다는 것 알았다.
그리고 답을 구할 때. b - a가 가장 크려면 a가 가장 작아야 한다.
이 말은 찾은 소수들 중 더해서 n이 나오는 가장 작은 소수가 정답이라는 것이라서.
for i in range(3, n, 2):
if num[i] == 1:
if num[n - i] == 1:
res.append((i, n - i, n - i - i))
break이 반복문을 처음 성립하게 하는 소수가 정답인 것이다.
import sys
num = [1] * 1000001
num[1] = 0
num[0] = 0
for i in range(2, 1000001):
for j in range(i + i, 1000001, i):
num[j] = 0
while True:
n = int(sys.stdin.readline().strip())
if n == 0:
break
res = []
for i in range(3, n, 2):
if num[i] == 1:
if num[n - i] == 1:
res.append((i, n - i, n - i - i))
break
if len(res) == 0:
print("Goldbach's conjecture is wrong.")
else:
print("{} = {} + {}".format(n, res[0][0], res[0][1]))
