[Baekjoon/백준][1929][C/C++] 소수 구하기

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

수학, 정수론, 소수 판정, 에라토스테네스의 체 문제.

1. 문제

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

1929번: 소수 구하기

[문제]

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

[입력]

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

[출력]

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

[예제 입력 1]

3 16

[예제 출력 1]

3
5
7
11
13

반응형

2. 풀이

'에라토스테네스의 체' 라는 알고리즘을 알고 있다면 쉽게 풀 수 있는 문제이다. 다음은 해당 알고리즘에 대한 설명 링크이다.

 

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4#rfn-2

에라토스테네스의 체 - 나무위키

 

* sieve[] 배열에 소수 여부를 판별하여 적어둔다. true인 경우 소수가 아니고, false인 경우 소수이다.

* for (int i = 2; i <= (int)sqrt(N); i++)에서, sqrt(N)까지의 수만 비교한 이유는 다음과 같다. 에라토스테네스의 체를 이용해 1~n까지의 소수를 알고 싶다면, n까지 모든 수의 배수를 다 나눠 볼 필요는 없다. 만약 n보다 작은 어떤 수 m이 m=ab라면 a와 b 중 적어도 하나는 n​이하이다. 즉 n보다 작은 합성수 m은 n​보다 작은 수의 배수만 체크해도 전부 지워진다는 의미이므로, n​ 이하의 수의 배수만 지우면 된다. 단적으로 1~100인 경우, 사실은 7의 배수 중 남아있는 49(7*7), 77(7*11), 91(7*13)만 더 지우면 끝난다. 만일 112(121)보다 큰 수가 있다면 11을 제외한 11의 배수를 지워야 하는데, 이 과정에서 최초로 지워지는 수는 121(112)이다. 그런데 이는 주어진 범위를 초과하는 수다.

3. 코드

#include <iostream>
#include <cmath>
using namespace std;

bool sieve[1000001] = {true, true, false}; 
//false인 경우가 소수. 즉, 0과 1은 소수에서 제외된다.

int main(int argc, char* argv[]) {
	/* Faster */
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	/* Input */
	int M, N; cin >> M >> N;

	/* Sieve of Eratosthenes */
	for (int i = 2; i <= (int)sqrt(N); i++)
		for (int j = 2 * i; j <= N; j += i)
			if (!sieve[j]) sieve[j] = true;

	/* Output */
	for (int i = M; i <= N; i++)
		if (!sieve[i]) cout << i << '\n';

	/* Return */
	return 0;
}

/* 
에라토스테네스의 체 

...
N = 100~120 : 10까지만 확인
N = 121~143 : 11까지만 확인
N = 144~168 : 12까지만 확인
N = 169~195 : 13까지만 확인
N = 196~224 : 14까지만 확인
...

*/