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

 알고리즘 문제 중에 소수 문제가 간혹 등장한다.

소수란, 1보다 큰 자연수 중에 1과 자기 자신만을 약수로 가지는 수이다.

어떤 수(N) 가 소수인지 확인하기 위해선 2부터 N-1까지의 모든 수로 나누어지지 않으면 소수인지 확인할 수 있다.

def isPrime(N):
    for i in range(2, N):
        if N % i == 0:
            return False
    return True

정석의 코드를 예시로 들어봤다!

하지만 위의 코드로 넓은 범위의 수를 모두 확인하려면 많은 시간이 걸리게 된다.

이때 사용하는 알고리즘이 바로 에라토스테네스의 체이다!

 

✨ 에라토스테네스의 체란? 
고대 그리스 수학자 에라토스테네스가 만든 소수를 찾는 방법으로
마치 체로 수를 걸러내는 것과 같아서 에라토스테네스의 체라고 부른다.
소수를 대량으로 빠르게 구할 수 있는 알고리즘이다!

 

  알고리즘

1. 가장 작은 수부터 시작한다.
2. 해당 수의 모든 배수를 찾고자 하는 범위까지 지운다.
3. 지워지지 않은 다음 수로 넘어간다.
4. 2번을 반복한다. 
5. 모든 반복이 끝나고 남아있는 수들이 소수

 

  구현

arr = [True] * (N_+1)

for i in range(2, int(N**0.5) + 1):
    if arr[i]:
        for j in range(i+i, N+1, i):
            arr[j] = False

탐색 범위가 N의 제곱근만큼인 이유는

대칭적으로 짝을 이룬다라는 원리를 이용하기 때문이다.

예를 들어서, 16이라는 수는 1 ×16, 2 × 8, 4 ×4, 8 × 2, 16 ×1로 표현할 수 있다.

앞서 말한 것처럼 소수는 1과 자기 자신만을 약수로 가지는 수이므로

약수가 존재하는지 확인하려면 자기 자신의 제곱근만큼만 확인하면 된다!

 

WoW

마무리는 알고리즘이 동작 원리를 보여주는 짤로 마무리하겠다!