에라토스테네스의 체

에라토스테네스의 체

임의의 자연수 이하의 존재하는 소수를 간단하고 빠르게 찾는 알고리즘

방법
(1제외) 2부터 임의의 자연수 A의 제곱근까지 각 배수를 제거하는 방법이다.
배수가 된다는 것은 소수가 아니기 때문이다.

def find_prime_list(A):
    number_list = [True for _ in range(A + 1)]	#각 인덱스는 자연수와 매칭됨
    for i in range(2, int(A**0.5) + 1):			#2부터 A의 제곱근 까지 반복
        if number_list[i]:						#중복 탐색을 줄이기 위한 조건ex(2와 4)
            for j in range(i**2, A + 1, i):		#A이하 까지 i의 배수를 제거
                number_list[j] = False
    return [i for i in range(2, len(number_list)) if number_list[i]]

print(find_prime_list(10)) #출력 값 : [2, 3, 5, 7]

여기서 A의 제곱근까지만 찾는 이유는 다음과 같다.
36을 예시로 36의 제곱근은 6이다.
6까지만 찾으면 되는 이유는 2부터 탐색을 시작할때

2 x 2
2 x 3 
.
.
.
2 x 18
---------
3 x 2
3 x 3
.
.
.
3 x 12

반대로 생각하면 7 x 2를 이미 제거했다.
계속 제곱근 5까지 진행하다 보면 7 x 3, 7 x 4 ... 7 x 5까지 이미 모두 제거를 한 상황이다.
따라서 제곱근 이상의 수는 이미 모두 제거된 상태다.