문제
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다.
예를 들어 8은 3 + 5로 나타낼 수 있고, 3과 5는 모두 홀수인 소수이다. 또, 20 = 3 + 17 = 7 + 13, 42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23 이다.
이 추측은 아직도 해결되지 않은 문제이다.
백만 이하의 모든 짝수에 대해서, 이 추측을 검증하는 프로그램을 작성하시오.
실패(시간초과) 코드
import sys
def isPrime(n):
if n < 2:
return False
elif n == 2 or n == 3:
return True
elif n % 2 == 0 or n % 3 == 0:
return False
for i in range(4, n):
if n % i == 0:
return False
return True
while True:
n = int(sys.stdin.readline())
if n == 0:
break
for i in range(n, 1, -1):
if isPrime(i):
if n - i == 1:
continue
print(f"{n} = {n-i} + {i}")
break
처음 무작정 풀었을 때는 시간 초과가 발생했다. n부터 1까지 -1씩 계속 돌면서 모든 수를 체크하고 있었다. 예를 들어 1 ~ 1000까지 검사하고 1001이 들어오면 또 1 ~ 1001까지 검사하고 이런 식으로 실행되다보니 시간초과가 발생하는 건 당연했다.
1부터 1,000,000까지 한 번만 모든 숫자를 탐색해서 홀수인지 아닌지 판별하고 이후 로직을 추가해야 한다.
문제에 나와있는 출력 부분 제대로 안 읽어서 'Goldbach's conjecture is wrong.' 출력하라는 부분도 빼먹음;
구글링 후 다시 짠 코드
import sys
# 에라토스테네스의 체
isPrime = [True] * 1000001
for i in range(2, 1001): # √10000000인 1000까지만 모든 수를 반복해서 소수를 찾으면 된다.
if isPrime:
for j in range(i + i, 1000001, i): # 2와 3은 어차피 소수, 4는 2로 만들어짐, 5도 소수 <- 이런 방식이기 때문에 i + i로 체를 더 빨리 만든다.
isPrime[j] = False
while True:
n = int(sys.stdin.readline())
flag = True # 입력받은 수를 소수의 합으로 나타 낼 수 없는 경우, 주어진 문장을 출력하기 위한 변수
if n == 0:
break
for k in range(3, n, 2):
if isPrime[k] and isPrime[n-k]: # 'n = 소수(k) + 소수(n-k)'이어야 함으로 두 수가 모두 소수인지 판별
if n-k == 1 or (n-k)%2 == 0: # n이 4일 경우 k가 3일 때 n-k는 1이 된다. 1은 소수가 아니기 때문에 n-k가 1일 경우를 잡아준다.
continue
print(f"{n} = {k} + {n-k}")
flag = False
break
if flag:
print("Goldbach's conjecture is wrong.")
에라토스테네스의 체를 사용했다. 전에 선형대수인가 자료구조인가 강의에서 슥 지나갔던 기억이 난다.
에라토스테네스의 체란 ?
1. 1부터 n까지의 숫자를 나열한다.
2. 소수가 아닌 1을 제거한다.
3. 2를 제외한 2의 배수를 제거한다. (2는 소수이므로)
4. 3을 제외한 3의 배수를 제거한다.
5. 4의 배수는 이미 2의 배수에서 지워졌으므로 반복할 필요가 없다.
6. 5를 제외한 5의 배수를 제거한다.
7. 7을 제외한 7의 배수를 제거한다.
8. 이와 같은 과정을 √n까지 반복한다.
이러한 해결 방법을 알고 나서도 범위가 1,000,000인데 100,000으로 잘못 입력하고, "Goldbach's conjecture is wrong." 출력 조건을 놓치는 등 자잘한 오류들로 시간을 꽤 잡아먹었다.
반응형
'Problem Solve > 백준' 카테고리의 다른 글
[Python] 백준 2609번 - 최대공약수와 최소공배수 (0) | 2024.03.27 |
---|---|
[Python] 백준 11656번 - 접미사 배열 (1) | 2024.03.27 |
[Python] 백준 10824번 - 네 수 (0) | 2024.03.27 |
[Python] 백준 11655번 - ROT13 (0) | 2024.03.25 |
[Python] 백준 10820번 - 문자열 분석 (0) | 2024.03.25 |