2023-07-07 TIL

[algoritm] 에라토스테네스의 체 : 소수 구하기

참고 문서 1
참고 문서 2

📕 개념

❓ 소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

에라토스테네스의 체는 소수를 빠르게 찾아내는 알고리즘의 한 종류이다.

🔎 구조

1. 2부터 종착점인 n까지 자연수를 늘어놓는다.
2. 먼저 2의 배수를 차례로 지운다.
3. 그러곤 3의 배수, 5의 배수... 이런식으로 남은 숫자들의 배수를 지워나간다.
4. n에 도착했을 때, 남아있는 모든 숫자는 소수이다.

n이 100일때는 이런식으로 지워져 나간다.

✅ python으로 적용시켜보기

👀 전체 코드

def eratos(num):
    arr = [False,False] + [True]*(num-1)
    eratos_arr = []

    for i in range(2, num+1):
        if arr[i] is True:
            eratos_arr.append(i)
            for j in range(2*i, num+1, i):
                arr[j] = False

print(eratos(100))

🔎 추가 설명

    arr = [False,False] + [True]*(num-1)

먼저, 길이가 num+1인 True 리스트를 생성해준다.
이유는 리스트의 index가 0부터 시작하기 때문이다.

처음엔 2부터 n까지의 모든 숫자가 소수라고 생각하고 전체에 True 값을 준다.
0과 1은 애초에 2보다 작기 때문에 소수의 전제조건을 만족할 수 없어 False로 둔다.

    for i in range(2, num+1):
        if arr[i] is True:
            eratos_arr.append(i)

숫자를 하나씩 순회하면서, True일 경우에만 실행 가능하게 조건을 걸어준다.
그러고 True값에 해당하는 숫자(소수)는 eratos_arr에 추가해준다.

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

이 부분이 핵심이라고 봐도 된다.

소수 i의 2배수부터 시작해서 마지막 값까지 순회하되,
i씩 증가해 i의 배수를 순회할 수 있게 한다.

그리고 배수를 False 처리해주면 된다.