[Algorithm] 에라토스테네스의 체는 뭐야?

에라토스테네스의 체는 소수의 배수들을 지우면서 소수를 찾는 방법이다. 해당 알고리즘에서 중요한 점은 만약 1부터 150까지의 소수를 구하고 싶다면 13^2 > 150 이므로 13보다 작은 수의 배수들만 지워주면 된다는 것이다.

 

에라토스테네스의 체는 다음의 과정으로 진행된다. 구하고자 하는 소수의 구간을 n, √n을 m이라고 한다.

 

1. n개의 배열을 생성해준다.
2. 2부터 m+1까지의 숫자들 중에 계산되지 않은 값을 확인한다.
3. 계산되지 않은 값이 있다면 해당 값의 배수들을 계산 처리하고, 2번의 과정으로 돌아간다.
4. 계산 처리되지 않은 값들을 출력한다.

위의 과정을 코드로 구현하면 다음과 같다.

 

def primeNumber(n):
  sieve = [True] * n
 
  m = int(n ** 0.5)
  for i in range(2, m+1):
    if sieve[i] == True:
      for j in range(i, n, i):
        if i != j:
          sieve[j] = False
  return [i for i in range(2, n) if sieve[i] == True]

 

백준 1978번 소수 찾기 문제를 예로 들어 실습을 해보겠습니다. 문제 해설

1978번: 소수 찾기

해당 문제는 1000(최댓값)까지의 소수를 모두 계산한 후에 주어진 수들이 소수 배열에 존재하는지 확인하는 것으로 해결할 수 있다. 해결 방법은 다음과 같다.

 

1. 에라토스테네스의 체 알고리즘을 사용하여 최대값 1000까지의 소수를 data에 저장한다.
2. data에서 입력받은 숫자들이 존재하는지 확인한다.
3. 존재한다면 count를 1 증가시켜주고, 아니라면 넘어간다.

에라토스테네스의 체 알고리즘의 시간 복잡도는 O(nloglogn)으로 빠르다는 장점이 있지만 숫자의 크기만큼 배열을 할당해야 하는 단점 또한 존재한다.

 

def primeNumber(n):
  sieve = [True] * n
 
  m = int(n ** 0.5)
  for i in range(2, m+1):
    if sieve[i] == True:
      for j in range(i, n, i):
        if i != j:
          sieve[j] = False
  return [i for i in range(2, n) if sieve[i] == True]
 
data = primeNumber(1000)
m = int(input())
value = list(map(int,input().split()))
 
count = 0
for i in range(m):
  if value[i] in data:
    count += 1
print(count)

 

에라토스테네스의 체는 주어진 범위에서 소수를 구하는 경우에 유용할 것으로 보인다.