🥈 6588 골드바흐의 추측
문제
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의 최대값인 1000000까지 미리 소수인지 판별해둔 다음, while loop를 돌아야한다. 매번 수가 들어올 때마다 소수판별을 하게되면 시간초과가 난다. 에라토스테네스의 체를 이용하여 소수 판별을 해주면 된다.
그리고 최대 입력값은 백만인데, 이하에서 참된 추측이라고하니, 나타낼 수 없는 경우에 출력하는 "Goldbach's conjecture is wrong."은 추가하지 않아도 된다.
소스 코드
import sys
input = sys.stdin.readline
def isPrime(n = 1000000):
Prime_numbers[0] = Prime_numbers[1] = False
for i in range(2, int(n * 0.5) + 1):
if Prime_numbers[i]:
for j in range(i * 2, n, i):
if Prime_numbers[j]:
Prime_numbers[j] = False
Prime_numbers = [True for _ in range(1000000 + 1)]
isPrime()
while True:
x = int(input())
if x == 0:
break
for i in range(3, x):
if Prime_numbers[i] and Prime_numbers[x - i]:
print(f"{x} = {i} + {x-i}")
break