[알고리즘] 에라토스테네스의 체

에라토스테네스의 체는 유명한 알고리즘입니다.

소수를 구하는 알고리즘인데요

소수란 자기자신과 1만을 가지는 정수입니다.

알고리즘:

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

에라토스테네스이 체

(출처:위키백과)

코드: Python3

## 에라토스테네스의 체 ##

def prime_list(n):
	check = [True] * (n+1) # 우리는 인덱스1부터 시작할 것이기에
    for i in range(2,int(n**0.5)) # n**0.5는 n의 2분의 1승을 나타낸다. **는 거듭제곱을 뜻함.
        if check[i] == True:
        for j in range(i*i,n+1,i) # 만약 i가 2면 4부터 시작, i는 2씩 증가한다.위 그림대로 배수들을 모두 지워나간다.
        	check[j] == False
        
	for k in rang(2,n+1):
    	if check[k] == True:
        	print(i)
prime_list(100) # 구하려는 범위의 최대값을 100에 있는 자리의 넣어주면 된다.