백준 6588 파이썬 : 골드바흐의 추측 (feat. 에라토스테네스의 체)

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

6588번: 골드바흐의 추측

< 소스 코드 >

# 소수여부 배열
arr = [True for i in range(1000001)]

## 에라토스테네스의 체
for i in range(2,1001): 
# 1001 == math.sqrt(1000000)+ 1 : 약수의 성질 (모든 약수가 가운데 약수 기준으로 곱셈연산에 대해 대칭)
  if arr[i]:
    for k in range(i+i, 1000001,i):
      arr[k] = False
      
while True:
  n = int(input())
  if n == 0:
    break
  for i in range(3,len(arr)):
    if arr[i] and arr[n-i]: # 둘다 소수면
      print(n,"=",i,"+",n-i)
      break

< 설명 >

'에라토스테네스의 체'를 사용해야 시간초과 에러에 빠지지않는다.

에라토스테네스의 체는 특정 범위 내의 소수를 판정하는 데에만 효율적인 소수판정법이다.

전체 배열을 두고 숫자 2 부터 그 수의 배수들은 소수가 아니라고 판정해나가면 된다.

 

흔한 소수 판정법(range(2,n) 나머지연산)을 개선한 게 약수의 성질을 이용해 range(2,math.sqrt(x)+1)을 쓰는건데,

이 문제는 에라토스테네스의 체를 구할 때에도 range(2,math.sqrt(x)+1) 으로 쓰는 것도 모자라

매번 범위를 벗어나지않았는지 확인하면서 math.sqrt(x) 를 실행하지않도록 그 값을 미리 변수에 저장해둬야했다.

에라토스테네스의 체를 통해 원하는 범위의 수들의 소수여부 정보를 갖는 배열을 얻고나면 아주 쉬운 문제가 된다.