[알고리즘 문제 풀이][파이썬] 백준 6588번: 골드바흐의 추측
백준 6588 문제 링크: https://www.acmicpc.net/problem/6588
📑 문제 설명
골드바흐의 추측: 4 이상의 짝수는 두 홀수인 소수의 합으로 나타낼 수 있음.
6보다 크거나 같고, 1000000보다 작거나 같은 짝수가 주어질 때, 주어진 수에 대해 홀수이자 소수로 이루어진 두 수를 구하는 프로그램 작성.
입력: 6보다 크고 1000000보다 작은 짝수(0을 입력시 프로그램 종료)
출력: "n = a + b" 로 출력. 만약 나타낼 숫자가 없다면 "Goldbach's conjecture is wrong." 출력
💡 문제 해결 방법
시간 초과를 유의해야 하는 문제.
key point
1. 소수를 구할 때는 에라토스테네의 체 를 사용한다.
2. 0 입력되기 전까지 소수를 구해야 하기 때문에 반복문 돌기 전에 한 번만 1000000이하의 소수를 구해놓는다.
(2번 때문에 시간초과 걸리는 줄도 모르고...😂)
💻 코드
import sys
if __name__ == '__main__':
t = -1
tf_list = [True for i in range(1000001)]
tf_list[0] = False
tf_list[1] = False
for i in range(2, 1001):
if (tf_list[i] == True):
for k in range(i + i, 1000001, i):
tf_list[k] = False
while(1):
t = int(sys.stdin.readline())
if t == 0:
break
check = -1
for i in range(3, t, 2):
if (tf_list[i] and tf_list[t - i]):
print(t, "=", i, "+", t - i)
check = 1
break
if (check == -1):
print("Goldbach's conjecture is wrong.")
💟 추가적으로 알게 된 점
- 시간 초과가 나는 이유를... 파악하자...
Author And Source
이 문제에 관하여([알고리즘 문제 풀이][파이썬] 백준 6588번: 골드바흐의 추측), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yeomja99/알고리즘-문제-풀이파이썬-백준-6588번-골드바흐의-추측저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)