소수 구하기(에라토스테네스의 체)

소수란?

소수는 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다.

소수 구하기

소수를 구하는 판별법으로는 에라토스테네스의 체를 들 수 있다.

에라토스테네스의 체 원리

1 ~ 30의 수 중 소수를 구하는 예시

1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.

   

2. 2부터 시작하고(1은 소수가 아님) 현재 숫자가 지워지지 않은 숫자이면 현재 선택된 숫자의 배수를 배열 끝(구하려는 최대 수의 제곱근)까지 탐색하면서 지운다. 이때 선택된 숫자는 지우지 않는다(선택된 숫자가 소수이다.).

   

3. 배열의 끝까지 2번 과정을 반복한 후 배열에서 남아있는 수(0이 아닌 수)가 소수이다.

   

에라토스테네스의 체 방식의 시간 복잡도는?

일반적으로 이중 for문을 사용하기 때문에 O(N^2) 라고 판단할 수 있지만,
평균적으로 최적화 정도에 따라 다르지만 O(Nlog(logN))이 나온다.
그 이유는 배수를 삭제하는 연산으로 실제 구현에서는 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문이다.