에라토스테네스의 체

어떤 수의 소수를 효과적으로 구하는 방법

 

 

원리

에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나가는 방법을 이용한다.

1. 배열을 생성하여 초기화한다.
2. 2부터 시작해서 숫자의 배수를 모두 1로 표기하면서 소거 
3. 1이 아닌숫자를 출력 = 소수