(파이썬) 백준 6588 골드바흐의 추측 파이썬 풀이

백준 6599번 문제

풀이

 

시간초과를 방지하기 위해 소수를 True, 소수 아닌 것을 False로 만든다.

1.

문제에서 6에서 1000000까지 주어진다 했으므로

a = [True for i in range(1000001)]

 

2.

소수는 1과 자신만을 약수로 가진 친구들, 그러면 2부터 구구단을 외우면서 False로 만들어 준다.

1001까지 하는 이유는 소수찾기에서 **0.5까지 범위 잡았던 것을 생각하면 된다.

int(1000001**0.5+1) = 1001이다.

 

for i in range(2,1001):

  if a[i]:

    for j in range(i+i,1000001,i):

      a[j]=False

 

3.

이젠 True인 친구들은 모두 소수다. for문은 작은 값부터 시작하므로, 먼저 나오면 출력하고 퇴장하면 된다.

또한, 마지막 값은 0으로 끝낸다고 했으니 0이 나오면 빠져나오게 만들어 준다.

while True:

  b = int(input())

  if b==0:

    break

  for i in range(3,len(a)):

    if a[i] and a[b-i]:

      print(b,'=',i,'+',b-i)

      break