[백준 문제] P6588 골드바흐의 추측(2차)
[백준 문제] P6588-골드바흐의 추측 2차 도전
[백준 문제] P6588-골드바흐의 추측 2차 시도
- 이번엔 boolean값으로 만든 다음에 코드를 실행해 보았으나 시간초과
- 아무래도 내가 짠 에라토스테네스의 체 코드가 느린거 같다.
# 소수의 위치에 True로 만들기
max = 1000000
primes = [False,False] + [True]*(max-1)
for i in range(2, max) :
for j in range(2*i, max, i):
primes[j] = False
# 0이면 멈추고 가장 차이가 많이 나는 소수의 합 계산하기
while True :
n = int(input())
# n이 0이면 멈추기
if n == 0 :
break
# x2-x1이 가장 큰 소수 찾기(for문 한번으로 짜기)
for i in range(max) :
if primes[i] == True :
j = n-i
if primes[j] == True :
print(n, "=", i, "+", j)
break
8
8 = 3 + 5
0
다른 사람 풀이 참고
MAX = 1000000
prime = [False for _ in range(MAX+1)]
for i in range(2, MAX+1):
if i*i > MAX:
break
if prime[i] is False:
for j in range(i*i, MAX+1, i):
prime[j] = True
while True:
n = int(input())
if n is 0:
break
for i in range(2, MAX+1):
if prime[i] is False:
j = n - i
if prime[j] is False:
print(n, "=", i, "+", j)
break
