[알고리즘] 에라토스테네스의 체

에라토스테네스의 체를 알기 전

에라토스테네스의 체란 소수를 구하는 알고리즘 기법이다.

에라토스테네스의 체를 알기 전만 해도 다음과 같이 소수를 구하였다.

def isPrime(a):
    if a < 2:
        return False
    for j in range(2, a):
        if a % j == 0:
            return False
    return True

for i in range(n + 1):
    if isPrime(i):
        print(i)    

isPrime은 소수인지 검사하는 함수이다.

1부터 100 사이의 소수를 구하는 코드인데, isPrime 함수에 1부터 100까지 하나씩 대입해서 소수인지를 확인한다.

isPrime 함수는 파라미터보다 작은 모든 수로 나누어서 소수인지를 판단하는 데, 소수의 정의에 해당하지만 효율적인 풀이는 아니다.

에라토스테네스의 체

범위에서 합성수를 지우는 방식으로 소수를 찾는 방법

1. 1은 제거
2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다.
3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다.
4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다.
5. (반복)

n = 1000
a = [False, False] + [True] * (n - 1)
primes = []


for i in range(2, n + 1):
  if a[i]:
    primes.append(i)
  for j in range(2 * i, n + 1, i):
    a[j] = False
print(primes)

참고 사이트

2. 소수 구하기 - 에라토스테네스의 체