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

 

그래프나 탐색 알고리즘뿐만 아니라, 코딩 테스트에서는 수학적 개념을 코드로 구현하는 문제도 자주 출제된다.
그중 대표적인 주제가 바로 소수 구하기이다.

소수는 정의 자체는 단순하지만, 입력 범위가 커질 경우 효율적인 판별 방법을 알고 있는지를 묻는 문제가 많다.

이번 글에서는 소수의 개념과 함께, 소수를 구하는 대표적인 알고리즘인 에라토스테네스의 체를 중심으로 정리해보려고 한다. ✍️

 

 

---

 

 

소수란?

소수(Prime Number) 란 1보다 큰 자연수 중에서, 자신보다 작은 두 자연수를 곱해 만들 수 없는 수를 말한다.

같은 의미로, 아래를 소수라고 정의한다.

• 1과 자기 자신 외에
• 약수가 존재하지 않는 수

예를 들어, 2, 3, 5, 7, 11 … 은 소수이지만 4(2×2), 6(2×3), 8(2×4) 등은 소수가 아니다.

 

코딩 테스트에서는 아래와 같은 형태로 자주 등장한다.
👉 “주어진 범위 내의 소수를 모두 구하라”
👉 “특정 수가 소수인지 판별하라”

 

---

 

 

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

소수를 구하는 대표적인 알고리즘으로는 에라토스테네스의 체(Sieve of Eratosthenes)가 있다.

에라토스테네스의 체는 소수가 아닌 수를 하나씩 지워가며 소수만 남기는 방식의 알고리즘이다.

하나씩 판별하는 방식보다 훨씬 효율적이기 때문에, 현재까지도 코딩 테스트에서 가장 일반적으로 사용된다.

 

 

---

 

 

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

1. 에라토스테네스의 체는 다음 과정을 따른다.
2. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다.
   숫자 2부터 시작하여,
   현재 숫자가 지워진 상태가 아니라면 해당 숫자의 배수들을 배열의 끝까지 탐색하며 지운다.
   (단, 자기 자신은 지우지 않는다.)
3. 배열의 끝까지 위 과정을 반복한 뒤,
   배열에 남아 있는 수들이 모두 소수가 된다.

이 방식의 핵심은 “소수가 아닌 수는 반드시 어떤 소수의 배수이다” 라는 점을 이용하는 것이다.

 

 

---

 

 

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

겉으로 보면 에라토스테네스의 체는 이중 for문을 사용하기 때문에 시간 복잡도가 O(N²) 처럼 보일 수 있다.

하지만 실제 시간 복잡도는 다음과 같다.

O(N log(log N))

 

그 이유는 다음과 같다.

• 이미 지워진 수는 다시 검사하지 않기 때문에
• 모든 수에 대해 배수 제거 연산이 수행되지 않는다.
• 특히 바깥쪽 반복문에서 불필요한 반복이 자연스럽게 생략된다.

이러한 특성 덕분에 에라토스테네스의 체는 큰 범위의 소수를 구할 때도 매우 효율적이다.

그래서 지금까지도 소수 구하기 문제의 표준적인 해결 방법으로 사용되고 있다.

 

+ 아래 문제들을 풀어 보시면 좋습니다!

https://www.acmicpc.net/workbook/view/3262