[Python] 에라토스테네스의 체 (Sieve of Eratosthenes)

1. 정의

- 2부터 시작하여, 소수인 경우 값을 출력하고, 해당 소수의 모든 배수들을 소거해 나가는 방법

 

2. 방법

- 2 -> 소수, N보다 작은 모든 2의 배수 제거

- 3 -> 소수, N보다 작은 모든 3의 배수 제거

- ....

- k -> 소수, N보다 작은 모든 k의 배수 제거

예를들어, 20까지의 소수 구하기를 한다면, 2의 배수부터 20까지의 배수를 지워주는 방식이다.

 

import time

def isPrime(v):
    i = 2

    while i*i < v:
        if v%i == 0:
            return False
        i += 1
    return True

try :
    k = input('Enter k: ')
    start = time.time()

    k = int(k)

    if k >= 2:
        primeList = list(range(k+1))
        primeList[1] = 0 # 1은 소수가 아니므로

        i = 2
        while i * 2 <= k:
            if primeList[i] != 0 and isPrime(i):
                for j in range(i*2, k+1, i):
                     primeList[j] = 0
            i += 1

        for prime in primeList: # 0은 소수가 아닌 숫자 이므로 0보다 크면 출력
            if prime > 0: print(prime, ' ')
    end = time.time() - start
    print('실행 시간: ', end)
except: 
    print('자연수가 아닙니다.')

 

---

 

4. 결론

- 소수를 구할 땐 에라토스테네스의 체를 이용하자