💡문제
1742년, 독일의 아마추어 수학가 크리스티안 골드바흐는 레온하르트 오일러에게 다음과 같은 추측을 제안하는 편지를 보냈다.
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을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.
예제입력
8
20
42
0예제출력
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37📖내가 실패한 Code
import itertools
def decimal_in_range(number):
decimal_list = set(range(3, number+1, 2))
for num in range(3, number+1):
decimal_list -= set(range(num*2, number+1, num))
return list(decimal_list)
def find_goldbach_number(number):
result_list = []
for a, b in itertools.combinations(decimal_in_range(number), 2):
if a+b == number:
result_list.append([a, b])
if len(result_list):
result_list.sort(key=lambda x: x[1]-x[0], reverse=True)
print(f'{number} = {result_list[0][0]} + {result_list[0][1]}')
else:
print("Goldbach's conjecture is wrong.")
def main():
while True:
number = int(input())
if not number:
break
find_goldbach_number(number)
if __name__ == '__main__':
main()
📖내가 작성한 Code
import sys
MAX_NUM = 1000000
def decimal_in_range():
decimal_list = [True] * (MAX_NUM + 1)
decimal_list[0], decimal_list[1] = False, False
for num1 in range(2, int(MAX_NUM**0.5) + 1):
if decimal_list[num1]:
for num2 in range(num1*num1, MAX_NUM + 1, num1):
decimal_list[num2] = False
return decimal_list
def find_goldbach_number(number, decimal_list):
for num in range(3, number+1):
if decimal_list[num] and decimal_list[number - num]:
print(f'{number} = {num} + {number - num}')
return
print("Goldbach's conjecture is wrong.")
def main():
decimal_list = decimal_in_range()
while True:
number = int(sys.stdin.readline())
if not number:
break
find_goldbach_number(number, decimal_list)
if __name__ == '__main__':
main()
✍️풀이과정
처음 생각 했던 풀이 과정은,
- 에라토스테네스의 체로 input 받은 만큼 체를 만든다
- 이하 모든 소수에 대하여, 조합한 후, 성공 조합을 저장한다.
- 제일 편차가 큰 수를 output한다.
였지만,
시간 초과가 나고 만다.
그래서 다음과 같이 수정하였다.
- 한 번 만들어놓은 에라토스테네스의 체를 재사용
- 모든 조합이 아닌, 낮은 숫자부터 찾아서 조합이 완성 되면 바로 output
하지만, 또 시간 초과가 나고 말았다.
그래서, 다시 내 코드의 시간 복잡도를 확인하니
def decimal_in_range(number):
decimal_list = set(range(3, number+1, 2))
for num in range(3, number+1):
decimal_list -= set(range(num*2, number+1, num))
return list(decimal_list)전체 리스트와 빼는 리스트 두 번 돌았기 때문에 사실상 O(n^2)여서 시간 초과가 나는 것이였다.
또한, 소수 판별 시 숫자 탐색이 O(n)이 였다는 사실도 알게 되었다.
따라서,
- 에라토스테네스의 체의 시간 복잡도를 줄이자
- 숫자 탐색을 인덱싱으로 하여 O(1)로 줄이자
로 귀결되었다.
따라서, 최댓값의 불리언리스트를 작성.
체에 거르는 최댓값을 int(MAX_NUM^0.5) + 1 값으로 하여, 시간 복잡도를 최소화
그런데 시간 초과가 났다
그래서 인터넷을 찾아보니,
sys.readline()이 부분만 해결하니까 성공하였다.
input() vs sys.stdin.readline()
- input() : 내부적으로 Prompt 처리(>>> 등), 문자열 버퍼링, EOF 예외처리,
그리고 개행 문자(\n)를 자동으로 제거하는 등의 추가 작업
- sys.stdin.readline() :sys.stdin.readline()은 이 스트림에서 “한 줄을 그대로” 가져오기만 하는, 단순한 함수
따라서, 백준 관련 문제를 풀 때는 sys를 생활화 하자
🧠 코드 리뷰
범위 축소 : find_goldbach_number(number, decimal_list) 함수에서 실제로는 number//2 + 1까지만 확인하면 충분. 또한, 2씩 뛰어넘어도 좋음.
🛠️AI 개선 코드
import sys
MAX_NUM = 1000000
def get_sieve_of_eratosthenes():
"""
1부터 MAX_NUM까지 에라토스테네스의 체를 이용해 소수 여부를 구해,
sieve[i] = True 이면 i는 소수, False면 소수가 아님.
"""
sieve = [True] * (MAX_NUM + 1)
sieve[0], sieve[1] = False, False # 0과 1은 소수가 아님
for i in range(2, int(MAX_NUM**0.5) + 1):
if sieve[i]:
# i*i부터 i의 배수를 모두 False 처리
for j in range(i * i, MAX_NUM + 1, i):
sieve[j] = False
return sieve
def print_goldbach_pair(n, sieve):
"""
골드바흐의 추측에 따라 짝수 n을 두 소수의 합으로 표현한다.
sieve는 'get_sieve_of_eratosthenes'로 만들어진 소수 여부 리스트.
"""
# (선택) n이 4 미만이거나 짝수가 아니면 골드바흐 쌍을 구성할 수 없으니 처리
# 문제 조건상 짝수만 들어온다면 필요 없지만 방어적으로 넣을 수도 있음
if n < 4 or n % 2 != 0:
print("Goldbach's conjecture is wrong.")
return
# 3부터 n//2까지만, 홀수만 검사 (2는 예외 소수이므로 고려 가능)
for p in range(3, (n // 2) + 1, 2):
if sieve[p] and sieve[n - p]:
print(f"{n} = {p} + {n - p}")
return
print("Goldbach's conjecture is wrong.")
def main():
sieve = get_sieve_of_eratosthenes() # 1회만 계산
while True:
line = sys.stdin.readline().strip()
if not line: # EOF 대비
break
n = int(line)
if n == 0: # 0이면 종료
break
print_goldbach_pair(n, sieve)
if __name__ == "__main__":
main()
💻결과
🖱️참고 링크
