[ Do it! 알고리즘 코딩 테스트 ] 정수론 - 소수 구하기

🔷 소수(Prime number)?

1과 자기 자신 외의 약수가 존재하지 않는 수를 의미한다.

 

🔷 소수를 구하는 판별법

에라토스테네스의 체 ( Sieve of Eratosthenes )

 : 소수들을 대량으로 빠르고 정확하게 구하는 방법

 

🔷 에라토스테네스의 체의 원리

🔻 구하고자하는 소수의 범위만큼 1차원 배열 생성한 뒤 초기화한다.

🔻 2부터 시작해서 현재 선택된 숫자의 배수의 해당되는 수를 모두 지운다.

(이때 자기자신은 지우지않으며, 이미 지워진 수는 건너뛴다.)

🔻 배열이 끝날 때까지 반복한 뒤 2부터 시작하여 남아 있는 수를 모두 출력한다

 

 

🔷 에라토스테네스의 체의 시간 복잡도

이중 for문을 이용하여 O(N^2) 으로 판단될 수 있지만 배수를 삭제하여 생략하는 경우도 있기 때문에 O(n * log(log n)) 이다.