[Algorithm] 38강 : 에라토스테네스의 체 알고리즘의 정의와 구현

에라토스테네스의 체 알고리즘 1.1 에라토스테네스의 체 알고리즘이란? 다수의 자연수에 대하여 소수 여부를 판별할 때 사용하는 대표적인 알고리즘이다. N보다 작거나 같은 모든 소스를 찾을 때 사용할 수 있다. 1.2 에라토스테네스의 체 동작 알고리즘 동작과정 2부터 N까지의 모든 자연수를 나열 남은 수 중에서 아직 처리하지 않은 가장 작은 수 I를 찾는다 남은 수 중에서 I의 배수를 모두 제거한다 더 이상 반복할 수 없을때까지 2번과 3번의 과정을 반복한다. 1.3 알고리즘 구현 import math n = 1000 array = [True for i in range(n + 1)] for i in range(2, int(math.sqrt(n) + 1)): if array[i] == True: j = 2 w..