1. 에라토스테네스의 체란?


소수를 찾는 알고리즘이다.

알아두면 알고리즘 문제를 풀 때 간간이 쓸모 있게 쓰이므로 숙지하도록 하자!!

2. 알고리즘 설명


출처: 위키백과: 에라토스테네스의 체

출처: 위키백과: 에라토스테네스의 체

  1. 소수를 구하고자 하는 구간의 모든 수를 2부터 나열한다.

  2. 2는 소수이므로 소수 리스트에 추가한다.

  3. 자기 자신을 제외한 2의 배수를 모두 지운다. (빨간색)

  4. 남아있는 수 가운데 3은 소수이므로 소수리스트에 추가한다.

  5. 자기 자신을 제외한 3의 배수를 모두 지운다. (연두색)

  6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.

  7. 자기 자신을 제외한 5의 배수를 모두 지운다. (파란색)

  8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.

  9. 자기 자신을 제외한 7의 배수를 모두 지운다. (노란색)

  10. 위의 과정을 재귀적으로 반복한다.

그림의 경우, 11^2 >120 므로 11보다 작은 수의 배수들만 지워도 충분하다. 즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다

3. 파이썬 소스코드


def prime_list_ver1(n):
    # 리스트 초기화 (전부 소수로 간주)
    sieve = [True] * (n+1)
    # n의 최대약수가 sqrt(n) 이하이므로 i = sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m+1):
        if sieve[i] == True: # i 가 소수인 경우
            # i 이후의 i의 배수를 모두 False로 판정
            for j in range(i+i, n+1, i):
                sieve[j] = False
    return [i for i in range(2, n+1) if sieve[i] == True]

def prime_list_ver2(n):

4. 암기 포인트


★1. 소수 구하기 문제는 " 구하고자 하는 수의 제곱근 < n (소수) " 가 포인트!

그 소수 n까지의 배수만 지워주면 된다.

★2. 구하고자 하는 수를 전부 소수로(True) 가정하고 소수에 배수에 해당할 경우 False로 바꿔주기

3.  True 인 친구들 전부 리스트로 뽑아주면 끝!