BOJ 1929 - 소수 구하기

문제 링크

문제#

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력#

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력#

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이#

구간 안의 소수를 여러 개 출력해야 하므로, 각 수를 하나씩 나눠 보는 것보다 에라토스테네스의 체로 미리 소수 여부를 구하는 편이 훨씬 효율적이다. 2부터 시작해 아직 지워지지 않은 수의 배수를 차례대로 제거하면 끝까지 남는 수가 소수다.

코드는 N까지의 소수 여부를 한 번 계산한 뒤, M 이상 N 이하 구간만 다시 순회하며 출력한다. 한 번 전처리를 끝내면 출력 단계는 단순 조회만 남는다.

코드#

#include <iostream>
using namespace std;
 
bool is_not_prime[1000001] = {};
 
int main() {
 
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int M, N;
	cin >> M >> N;
 
	is_not_prime[0] = true;
	is_not_prime[1] = true;
 
	for (int i = 2; i < N + 1; i++) {
 
		for (int j = 2 * i; j <= N + 1; j += i) {
			if(!is_not_prime[j])
				is_not_prime[j] = true;
		}
	}
 
 
	for (int k = M; k < N + 1; k++) {
		if (!is_not_prime[k])
			cout << k << '\n';
	}
 
	return 0;
}

복잡도#

• 시간 복잡도: 에라토스테네스의 체를 사용하므로 $O(M \log \log M)$이다.
• 공간 복잡도: 소수 여부 배열을 저장하므로 $O(M)$이다.

마무리#

구간 안의 소수를 여러 개 출력해야 하므로, 각 수를 하나씩 나눠 보는 것보다 에라토스테네스의 체로 미리 소수 여부를 구하는 편이 훨씬 효율적이다.