에라토스테네스의체

[코드업] 3071. 구간에서의 소수 찾기

문제 설명 문제풀이 KEY POINT 에라토스테네스의 체를 사용한 문제였다. 에라토스테네스의 체 알고리즘이란? 1. 2부터 N까지 모든 자연수 나열 후 전체 True처리 2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 (i) 찾음 3. 남은 수 중에서 i의 배수를 모두 False 처리 4. 반복할 수 없을 때까지 2,3번 과정 반복 위 과정으로 진행되는 알고리즘으로, 배열 내 소수 찾기에 주로 사용된다. import math n = 1000 # 2부터 1,000까지의 모든 수에 대하여 소수 판별 array = [True for i in range(n + 1)] # 처음엔 모든 수가 소수(True)인 것으로 초기화 # 에라토스테네스의 체 알고리즘 for i in range(2, int(math.sq..