소수 구하기

소수 Prime Number

 

1과 자기자신만 약수로 갖는 1보다 큰 자연수

 

소수 구하기의 핵심이론: 에라토스테네스의 체

1. 구하고자 하는 소수의 범위만큼 1차원 리스트 생성

2. 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우,

현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하고 제거함

(** 첫 숫자는 지우지 않음!)

3. 리스트의 끝까지 2 반복 후 리스트에 남아 있는 모든 수 출력