[Algorithm]에라토스테네스의 체 - 소수 판별하기

에라토스테네스의 체는 뭘까?

가장 대표적인 소수를 판별하는 알고리즘이다.

소수를 대량으로 빠르고 정확하게 구하는 방법이다.

 

일반적으로 소수를 구하는 알고리즘의 시간복잡도는 O(N)이다.

BUT 에라토스테네스의 체를 사용하게 되면 시간복잡도를 O(N^(1/2))로 줄일 수 있다.

 

에라토스테네스의 체의 원리?

모든 약수들을 대친 형태를 이룬다는 점에서 가능하다.

예를 들어, 8의 약수인 2와 4를 보면 2\*4 = 4\*2 식에서 대칭인 것을 발견할 수 있다.

 

따라서 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 된다.

위의 예시로 다시 설명하면, 8의 약수를 구하기 위해서는 1, 2만 보면 된다. (8=2루트2)

 

🚩 하나의 소수 판별

def is_prime(x):
    end = int(x ** 0.5)
    for j in range(2, end+1):
        if x % j == 0:
            return False
    return True

 

에라토스테네스의 체 구현!

🚩 여러 개의 소수 판별

 

1. 이차원 배열을 생성해 값을 초기화 (소수를 판별할 범위만큼 배열 할당)

1	2	3	4
5	6	7	8
9	10	11	12

2. 2부터 시작해서 특정 숫자의 배수는 다 지워버려~

    BUT 자기 자신은 지우지 않음 (ex. 2, 3)

1	2	3	4
5	6	7	8
9	10	11	12

3. 2부터 시작해서 남아 있는 숫자들 다 출력

> 2 3 5 7 11

 

def is_prime_sieve(n):
    # 에라토스테네스의 체 초기화 - 일단 다 True(소수)라고 간주
    sieve = [True] * n

    m = int(n ** 0.5)     # 제곱근까지만 계산
    for i in range(2, m + 1):
        if sieve[i] == True:     # i가 소수인 경우
            for j in range(i + i, n, i):     # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

 

숫자들이 체에 걸려진거 같다고 해서 알고리즘 이름이 "에라토스테네스의 체"이다.

이런걸 생각해내는 사람들이 신기하다. 

재밌네!! 

 

 

참고 
https://youtu.be/5ypkoEgFdH8
https://this-programmer.tistory.com/409