백준(Python) 풀이/수학

백준(Python) 6588번 골드바흐의 추측 풀이

개발윗미 2021. 10. 12. 10:44

Python으로 구현한 6588번 골드바흐의 추측 문제 풀이입니다.

 

https://www.acmicpc.net/problem/6588

 

6588번: 골드바흐의 추측

각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰

www.acmicpc.net


import sys

num = 1000001
data = [True for _ in range(num)]
for i in range(2, int((num-1)**0.5) + 1) :
  if data[i] :
    for j in range(i + i, num, i) :
      data[j] = False
 
while True :
  n = int(sys.stdin.readline())
  if n == 0 :
    break
  
  count = 0
  for i in range(3, len(data)) :
    if data[i] and data[n-i] :
      print(str(n) + " = " + str(i) + " + " + str(n-i))
      count = 1
      break

  if count == 0 :
    print("Goldbach's conjecture is wrong.")

 

1000000까지 각 소수 여부를 구한 뒤 입력받은 n이 0이 아닐 경우에 while문을 계속해서 수행한다.

 

while문 내부에서는 다시 for문을 통해 해당 값이 참(소수)이고 n-i 번째 값 또한 참(소수)이라면 문제에서

 

요구하는 출력 형식에 맞게 값들을 출력한다. 또한, count 값을 1로 갱신한 뒤 count 값을 확인하여 그 값이 0이라면

 

두 홀수 소수의 합으로 n을 나타낼 수 없기 때문에 위와 같은 문구를 출력한다.