에라토스테네스의 체 소수를 구하는 알고리즘 문제에서 주로 사용되는 풀이 방식이다. 1. 2 ~ N 까지의 자연수들 중에서, 아직 지워지지 않은 수들 중에서 가장 작은 수를 찾는다. 이를 p 라고 한다. 2. p는 소수이므로 지우지 않고 남겨준다. 3. p 의 배수들을 하나씩 지워나간다. 1 ~ 3 의 과정들을 반복하면 결국 소수들만 남게 된다. ex) 2는 소수이므로 지우지 않고 , 4, 6, 8 ... 은 지워나가기 위의 그림을 참고하면 이해가 빠르다 N = 1000000 primes = [True] * (N+1) # 소수 primes[0] = False # 0 은 자연수 아님 primes[1] = False # 1은 소수 될 수 없음 for i in range(2, N+1): if primes[i]:..
