소수 구하기 (feat. 백준, 1929번)

소수 구하기
https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/1929
#include <iostream>
#include <cmath>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int M, N;
	register bool arr[1000001] = { false };
	cin >> M >> N;
	arr[0] = arr[1] = true;
	register int e = sqrt(N);
	for (register int i = 2, j; i <= e; ++i)
		if (!arr[i])
			for (j = i << 1; j <= N; j += i)
				arr[j] = true;
	for (register int i = M; i <= N; ++i)
		if (!arr[i])		cout << i << "\n";
	return 0;
}
// *&)*@*

2부터 N까지의 소수를 모두 구한 뒤, M ~ N 중 소수인 것들만 출력하면 됩니다.

이 또한 "에라토스테네스의 체" 로 미리 소수를 구했습니다. 아래 문제를 선행하시길 권장합니다.

소수 찾기 (feat. 백준, 1978번)