[파이썬/python] 에라토스테네스의 체

에라토스테네스의 체는 고대 그리스 수학자인 에라토스테네스가 고안해 낸 소수를 찾는 방법이다.

마치 체로 걸러내듯이 수를 걸러낸다고 하여 붙여진 이름이다.

임의의 자연수 n에 대해 소수를 찾는 가장 빠르고 간단한 방법이다.

 

소수를 찾아내는 원리는 2부터 시작하여 그의 배수를 지워나가는 방법으로 

다음으로 오는 가장 빠른 수를 대상으로 그 수의 배수를 계속해서 지워나간다.

그 후 남은 숫자들이 소수가 되는 것이다.

 

그렇다면 이제 이 과정을 몇 번 반복할지 정해줘야하는데

가장 큰 수가 올 때까지 반복해도 가능은 하겠지만 효율적이지 않다.

최소로 반복하는 방법은 제곱근을 이용하는 것이다.

 

이 문제에서 제곱근이 쓰이는 이유를 소인수분해를 이용하여 설명해보았다.

어떤 수의 제곱근이란 제곱하여 그 수가 되는 수로, 예를 들어 9의 제곱근은 3이다.

어떤 수의 약수를 구하면 제곱근을 제외한 모든 수는 짝을 이루어 그 어떤 수를 만든다.

예를 들어 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이고 36의 제곱근은 6이다.

 

제곱근을 기준으로 왼쪽에 있는 숫자는 오른쪽에 있는 수와 짝을 이루고 있다.

오른쪽에 있는 수는 왼쪽에 있는 짝의 배수로 에라토스테네스의 체를 이용하면 걸러질 숫자들이다.

따라서 에라토스테네스에 적용될 가장 큰 수는 제곱근보다 작거나 같은 숫자일 것이다.

 

이제 파이썬을 이용하여 소수구하는 방법을 구현해 볼 것이다.

소수구하기 예제는 백준 문제풀이에서 포스팅해두었다.

2021.03.09 - [🔍알고리즘/백준] - [백준/python] 1929번 : 소수 구하기

[백준/python] 1929번 : 소수 구하기

 

파이썬으로 구현하기

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

for index in range(M, N+1):
    if number[index] and index!=1:
        print(index)

M부터 N까지의 숫자 중 소수를 구할 것이다. number에는 N+1개의 True를 저장해두었다.

인덱스 숫자를 이용하기 때문에 N+1까지 해줘야 0부터 N까지의 숫자가 생긴다.

이제 에라토스테네스의 체를 이용하여 소수가 아닌 숫자들은 False로 바꾸어줄 것이다.

 

여기서 주의할 점은

💥 1은 소수가 아니기 때문에 지우고 시작해야한다는 점과

💥 나누는 수는 소수이기 때문에 그 수는 빼고 지워야한다는 점이다. (ex. 2의 배수를 지울 때 2는 빼고 지워야한다.)

 

2부터 N의 제곱근인 N**0.5보다 1큰 수 만큼 반복한다.

False로 바뀐 수는 더이상 볼 필요 없으므로 True인 숫자만 반복하기 위해 if문으로 걸러준다.

for j in range(2*i, N+1, i):
            number[j] = False

나누는 수는 False로 바꾸면 안되기 때문에 범위를 2*i부터로 설정하고

배수를 찾기 위해 step을 i로 설정해 덧셈으로 배수를 구현하여 해당 숫자를 False로 바꿔준다.

 

위 과정을 반복하면 number에는 소수인 숫자는 True로, 아닌 숫자는 False로 설정된다.

for index in range(M, N+1):
    if number[index] and index!=1:
        print(index)

이제 M부터 N의 범위에 있는 True의 인덱스를 출력해준다.

여기서 주의할 점은 1은 제외하고 출력해주어야 한다는 점이다.