에라토스테네스의 체-백준 9020, 1016

에라토스테네스의 체

소수를 찾아내는 가장 쉽고 정확한 방법. 모든 소수에 대해 자신의 배수를 전부 지워나가면 된다.

 

def Eratosthenes(n):
  high=int(n**0.5)
  isPrime=[1 for i in range(n+1)]
  isPrime[0]=0
  isPrime[1]=0
  for i in range(2, high):
    if isPrime[i]==1:
      for j in range(i**2, n+1, i):
        if isPrime[j]==1:
          isPrime[j]=0
  for i in range(n+1):
    if isPrime[i]==1:
      print(i)

 n까지의 소수를 전부 출력하는 코드. 최적화를 위해서는 2부터 최댓값의 제곱근까지만 반복하면 되며, 각각의 소수에 대해 자신의 제곱부터 지워나가면 된다.(ex) 5의 경우 25부터 보면 된다. 10, 20은 2 조사 과정에서, 15는 3 조사 과정에서 벌써 지워졌기 때문)

 

응용

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

9020번: 골드바흐의 추측

골드바흐 파티션을 찾기 위해서는 우선적으로 그 수보다 작은 모든 소수를 찾아내야 한다. 이는 에라토스테네스의 체를 이용해 간단하게 구할 수 있다.

어차피 짝수=홀수+홀수이므로 골드바흐 파티션을 이루는 소수 중 2가 걸릴 리 만무하며, 차가 가장 작은 소수 2개를 찾고 싶다면 n/2부터 탐색하면서 가장 처음으로 확인하는 소수의 쌍을 return하면 된다.

import sys

def Eratosthenes(n):
  high=int(n**0.5)
  isPrime=[1 for i in range(n+1)]
  isPrime[0]=0
  isPrime[1]=0
  for i in range(2, high+1):
    if isPrime[i]==1:
      for j in range(i*i, n+1, i):
        isPrime[j]=0
  return isPrime

def findPrime(n):
  Primes=Eratosthenes(n)
  for i in range(n//2, n+1):
    if Primes[i]==1:
      if Primes[n-i]==1:
        return (n-i, i)

T=int(sys.stdin.readline())
for i in range(T):
  n=int(sys.stdin.readline())
  ret=findPrime(n)
  print(ret[0], ret[1])

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

1016번: 제곱 ㄴㄴ 수

에라토스테네스의 체를 응용해서 푸는 문제. 제곱ㄴㄴ수의 정의를 보면 알겠지만, 에라토스테네스의 체에서 소수와 그 배수 대신에 제곱수와 그 배수들을 지워나가면 제곱ㄴㄴ수만이 남는다.

min의 범위가 매우 크기 때문에, 정석대로 1부터 검사하면 메모리 초과가 뜬다. 이를 막기 위해서는 배열의 크기를 딱 필요한 만큼(=max-min+1만큼) 만들면 된다. 그 이후 검사 대상인 제곱수들에 대해 그 제곱수의 배수들 중 min보다 큰 최솟값을 전부 구하고, 거기서부터 검사하면 된다.

import sys

def Jjabratostenes(a, b):
  isnSq=[1 for i in range(b-a+1)]
  hi=int(b**0.5)
  sq=[]
  for i in range(2, hi+1):
    sq.append(i**2)
  for i in sq:
    k=a
    if k%i!=0:
      k=(a//i+1)*i
    for j in range(k, b+1, i):
      if isnSq[j-a]==1:
        isnSq[j-a]=0
  print(sum(isnSq))

a, b=map(int, sys.stdin.readline().split())
Jjabratostenes(a, b)