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

고대 그리스 수학자인 에라토스테네스가 발견한 알고리즘이다. 그 시대에 어떻게 발견했나 싶네..

여러개의 소수를 상대할 때 좋은 알고리즘이다.

 

소수는 1과 자기자신으로 밖에 나눠지지 않는 수이다. (1 제외)

숫자 N의 소수판별은 N을 N의 제곱근이하인 수로 나눴을 때 나눠지지않았을 경우 소수이다.

# N 이하의 소수를 찾으려할 경우
# 소수는 1혹은 자기 자신으로 밖에 나눠지지 않는 수 이다.

# 0 - N 까지를 표현해줄 리스트 생성
arr = [True for _ in range(N+1)]

for i in range(2, int(N**0.5)+1):
        if arr[i]:
            for j in range(i*2, N+1, i):
                arr[j] = False
    # 0, 1은 소수가 아니기에 제외
print([i for i in range(2, N+1) if arr[i]])