[C / C++] 백준 1929번 - 소수 구하기 / 에라토스테네스의 체

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---

✅ 문제 설명

정수 M과 N을 입력하면,

M ~ N 사이의 소수를 출력하는 문제이다.

---

✅ 알고리즘 설명

처음에는 단순하게 생각하여,

M ~ N을 차례로 하나씩 나눠지는 수가 있는지 검사하여 출력하는 방식을 사용했다.

그러나 이 방법을 사용하면 시간복잡도가 O(N^2)으로 시간초과가 나게 된다.

 

따라서 이 문제에서는 '에라토스테네스의 체' 방식을 사용했다.

 

💡 에라토스테네스의 체 (Sieve of Eratosthenes) 💡
소수를 발견하면 그 소수의 모든 배수를 소수가 아니라고 체크한 후,
체크되지 않은 수를 출력하는 방식이다.

 

이 문제에 대입하여 좀 더 자세히 설명하면 다음과 같다.

 

1. 배열의 크기

이 문제의 경우 최대 1,000,000 까지 입력할 수 있다고 했고,

M ~ N 사이의 수만 고려하면 되기 때문에 배열의 크기를 1,000,001로 정했다.

 

2. 소수인지 점검하는 반복문

소수가 아닌 1을 제외하고, 2부터 sqrt(N)까지 차례로 소수인지 확인한다.

(나 같은 경우에는 sqrt()를 사용하지 않고, i * i <= n 을 사용했다.)

 

만약 소수일 경우,

그 숫자의 모든 배수를 소수가 아니라고 표시하면 된다.

 

3. 소수인지 출력하는 반복문

M ~ N 사이의 배열에서 소수가 아니라고 표시된 것을 제외하고 출력하면 된다.

 

만약 2부터 N사이의 소수를 출력하는 문제라면

2번 반복문에서 바로 출력해도 되지만,

이 문제의 경우 M ~ N 사이의 소수이기 때문에 따로 반복문을 만들었다.

 

아래의 그림을 보면 이해가 더 잘 되니 참고!

---

✅ 코드_C++