BOJ-백준 6588번 골드바흐의 추측

BOJ-백준 6588번 골드바흐의 추측

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

6588번: 골드바흐의 추측

 

✅ Python 정답 코드 입니다. 더보기 클릭!

import sys
input = sys.stdin.readline
print = sys.stdout.write
x = -1
nums_e = []
while 1:
  x = int(input())
  if x != 0:
    nums_e.append(x)
  else:
    break

def isPrime(num):
  for i in range(2, int(num**(1/2))+1):
    if num%i == 0:
      return False
  return True

sosu = [False]*1000001
for num in range(3,1000001):
  if isPrime(num):
      sosu[num] = True

for goldbach in nums_e:
  for a in range(goldbach):
    if sosu[a] and sosu[goldbach-a]:
      print(f"{goldbach} = {a} + {goldbach-a}\n")
      break

 

📌 해설

이해하기 어려운 이론은 아니었으나, 시간 제한이 있음을 고려하면서 풀어야 하는 문제 입니다.

주어지는 정수  n은 최대 1000000이며 테스트케이스는 100,000개 까지 최대로 입력 될 수 있습니다.

따라서 모든 테스트케이스에 대해서 소수를 구하지 않아야 하며,  

각 테스트케이스에서 소수에 조회를 한 번만 하고 a와 b를 구할 수 있어야 합니다. 

 

🚩주의

소수는 bool 타입의 list 변수를 1000001개를 초기화 하여 프로그램 실행시 모든 소수를 1회만 구합니다.

각 테스트케이스는 for 문을 한번만 돌면서 a와 b를 모두 구합니다. b = n-a 입니다. 

 

import sys
input = sys.stdin.readline
print = sys.stdout.write
x = -1
nums_e = []
while 1:
  x = int(input())
  if x != 0:
    nums_e.append(x)
  else:
    break

1. 모든 테스트케이스를 입력받아 nums_e에 저장합니다.

 

def isPrime(num):
  for i in range(2, int(num**(1/2))+1):
    if num%i == 0:
      return False
  return True

sosu = [False]*1000001
for num in range(3,1000001):
  if isPrime(num):
      sosu[num] = True

2. 1000001만큼 선언된 sosu list에 소수를 구해 소수인 index를 True로 변경합니다.

2-1. 1000001까지의 소수를 구하는 과정 역시 많은 시간을 소요하기 때문에 num**(1/2)까지만 약수를 확인합니다. 

2-2. 2는 소수지만 a, b가 될 수 있는 수는 홀수 이므로 2는 False로 남겨 놓았습니다. 

 

for goldbach in nums_e:
  for a in range(goldbach):
    if sosu[a] and sosu[goldbach-a]:
      print(f"{goldbach} = {a} + {goldbach-a}\n")
      break

3. nums_e에 저장된 모든 테스트 케이스를 순회하는 for 문을 작성합니다. 

3-1. 각 테스트케이스(goldbach) 만큼만 sosu를 조회합니다. 

3-2. 만약 sosu[a]가 True이고, b = goldbach-a이므로 sosu[goldbach-a]도 True이면, a와 b가 소수입니다.

3-3. 가장 먼저 찾아지는 수식( goldbach = a + b )을 출력하면   break를 통해 다음 테스트케이스로 이동 할 수 있도록 합니다.

3-4. 모든 테스트케이스를 돌 때 까지 반복합니다.

 

::