[개념정리] 소수 구하기

[YubinShin]

소수 구하기

Prime Number
수학적인 코테 문제가 나왔을 때 굉장히 빈번하게 출제되는 유형입니다.
1과 자신 외에 약수가 존재하지 않는 수를 말합니다.
대부분 코딩테스트에선 에라토스테네스의 체 원리로 구하게 됩니다.

시간복잡도

O(n log log n)

이중 for문을 사용하기에 O(n²) 일거 같지만, 배수를 삭제하는 과정에서 생략되는 반복이 빈번하기 때문에 확 줄어듭니다.
이 복잡도는 대략적으로 이해하기 위해 O(n) 보다는 조금 더 빠르지만 O(nlogn) 보다는 느린 것으로 볼 수 있습니다.

방법

에라토스테네스의 체

1. 구하고자 하는 소수의 범위 만큼 1차원 배열을 생성합니다.
2. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택한 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지웁니다. 이때 처음으로 선택된 숫자는 지우지 않습니다.
3. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수(소수)를 출력합니다.