[Python] 백준 6588 - 골드바흐의 추측

문제 보러 가기

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

사진을 클릭해도 해당 문제 사이트로 이동합니다.

해결방법

'에라토스테네스의 체'를 이용해서 풀었다. boolean 값을 담고 있는 sosu라는 리스트를 만들어서 2~len(sosu) 까지의 범위를 다 찾아보며 i번째 인덱스가 소수(True)일때를 두고 풀었다.

# 소수 판정
sosu = [True] * 1000001
m = int(1000001**0.5)
for i in range(2,m+1):
  if sosu[i]:
    for k in range(i+i,1000001,i):
      sosu[k] = False

while True:
  n = int(input())
  if n==0:
    break
  else:
    for i in range(2,m+3):
      if sosu[i] and sosu[n-i]:
        print("%d = %d + %d"%(n,i,n-i))
        break

처음에는 while문 안에서 n을 입력받아서 n이 새로 입력될 때마다 소수 판정을하도록 코드를 짰다. 시간 초과가 나오는 것을 보고 비효율적인 코드란 걸 뒤늦게야 깨달았다. 입력의 범위보다 살짝 크게 해서 입력으로 줄 수 있는 모든 수들에 대해 미리 소수 판정을 한 뒤에 입력받고 해당 인덱스만 따져보면 그만인 것이었다.

글을 쓰면서 드는 생각인데 ' for i in range(2, m+3): ' 에서 range부분만 range(3, m+3,2)으로 바꾸어주면 2배 향상된 속도로 답을 구할 수 있을 것으로 기대된다.

코드 설명

1. # 소수 판정

이 파트는 '에라토스테네스의 체'를 통해 구현한 것이다.

n = int(input())
sosu = [True] * n
for i in range(2,int(n**0.5)+1):
  if sosu[i]:
    for k in range(i+i,n,i):
      sosu[k] = False

sosu의 i번째 인덱스가 만약 True 값을 가지면 i는 소수인 것이다. 그리고 i+i부터 n까지의 i의 배수들은 모두 i로 나누어 떨어지므로 소수가 아니다. 그래서 sosu[i]가 True값을 가지면 sosu[k]는 전부 소수가 아니다.

단 위와 같이 range(2, int(n**0.5)+1)을 하게 되면 반복을 한 번 할 때마다 int(n**0.5)+1을 계속 계산하게 되므로 비효율적인 코드가 된다. 따라서 이런 계산이 꼭 필요하지 않는 이상은 새로 변수에 계산한 결과를 담아서 반복문을 돌리자.

2. 반복문

    for i in range(2,m+3):
      if sosu[i] and sosu[n-i]:
        print("%d = %d + %d"%(n,i,n-i))
        break

위 코드에서 'sosu[i] and sosu[n-i]' 이 조건식은 'i와 n-i 모두 소수인가?'라는 조건식이다. n = i+(n-i) 이므로 i와 n-i가 소수인지만 따지면 되기 때문이다.

그리고 break를 걸어둔 이유는 정답 출력 이후에 불필요한 반복을 하지 않기 위해서이다.

3. 빠진 조건?

 두 홀수 소수의 합으로 n을 나타낼 수 없는 경우에는 "Goldbach's conjecture is wrong."을 출력한다.

라는 조건이 있었다.

처음에는 이 조건을 생각하여 아래와 같은 코드를 작성했었다. 하지만 결국 이 코드를 빼버렸다.

    go = True
    for i in range(2,m+3):
      if sosu[i] and sosu[n-i]:
        print("%d = %d + %d"%(n,i,n-i))
        go = False
        break
    if go:
      print("Goldbach's conjecture is wrong.")

그 이유는 "우선, 골드바흐의 추측은 아직 아직도 해결되지 않은 문제이다. 즉, 이미 예전부터 컴퓨터로 진작에 돌려봤다는 얘기이고, 이 문제에서 주는 범위 내의 수들은 모두 말할 것도 없이 참인 경우이다."라고 생각했기 때문이다.

---