에라스토테네스의 체
자연수를 순서대로 늘어놓은 표에서 합성수를 차례로 지워나가면서 소수 목록을 얻는 알고리즘.
위키피디아에서 가져온 에라스토테네스의 체 알고리즘의 pseudocode는 이런 방식이다. input을 n이라고 할 때, 검사는 1 ~ n이 아닌 1 ~ n의 제곱근까지만 하면 된다. 어차피 n보다 크면 n보다 작은 수로 합성수를 찾아낼 때 이미 걸려지기 때문이다.
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.
let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
set A[j] := false
return all i such that A[i] is true.
파이썬으로 구현해 보자. 제곱근 함수를 사용하기 위해 math를 import 하였다. n이 일보다 작거나 같으면 빈 리스트를 반환해주면 되고, 가장 처음의 리스트에서는 처음 소수인 2를 넣어주었다. 그리고 검사의 한계는 n의 제곱근인 sqrt(n)으로 한정했다. 그 뒤 검사할 데이터를 2 부터 n 까지 2 단위로 i를 뽑아 낸 뒤, i+1의 값을 주어 리스트를 완성시켰다. n이 10일 때, 아직 limit에 대해 사용하지 않았으므로 함수의 결과값은 [3, 5, 7, 9]가 된다.
import math
def eratosthenes_sieve(n) :
if n <= 1 :
return []
prime = [2]
limit = int(math.sqrt(n))
data = [i+1 for i in range(2, n, 2)]
return data
tmp = eratosthenes_sieve(10)
tmp
[3, 5, 7, 9]
2로 나뉘었을 때 2로 나뉘어지는 짝수들은 제거한 data라는 리스트에서 이제 소수 판별을 계속 진행한다. data 리스트의 맨 처음 요소를 prime 리스트에 추가시키고 (즉 3을 추가함), data 리스트에서 해당 값으로 나뉘어지지 않는 모든 요소만 남겨 둔다. 계속 판별하는데, 상한선을 아까 지정해준 limit까지로만 설정하면 알고리즘이 완성된다. 남은 prime 리스트와 data 리스트를 합쳐서 반환하면 소수만 판별이 가능하다.
import math
def eratosthenes_sieve(n) :
if n <= 1 :
return []
prime = [2]
limit = int(math.sqrt(n))
data = [i+1 for i in range(2, n, 2)]
while limit >= data[0] :
prime.append(data[0])
data = [j for j in data if j % data[0] != 0]
return prime + data
tmp = eratosthenes_sieve(10)
tmp
[2, 3, 5, 7]
참고한 책과 사이트 :
가장 쉬운 독학 알고리즘 첫걸음 - 파이썬 편
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Sieve of Eratosthenes - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search Ancient algorithm for generating prime numbers Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square). In mathematics, the
en.wikipedia.org
'Python study > Basic algorithms' 카테고리의 다른 글
[Python] Bubble sort (버블 정렬) (0) | 2023.09.01 |
---|---|
[Python] generator 와 itertools (0) | 2023.08.31 |
[Python] map 과 lambda (0) | 2023.08.28 |
[Python] 파이썬 - 재귀 호출로 피보나치 함수 작성하기 (0) | 2022.08.10 |
[Python] 파이썬 - 리스트 내포 (List comprehension) (0) | 2022.07.31 |