[백준] 1929번 : 소수 구하기

문제

 

---

풀이

 

에라토스테네스의 체를 이용해 소수를 구하는 문제다. 에라토스테네스의 체가 무엇이냐고 물어본다면...

출처 : 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

이런식으로 특정 소수의 배수를 전부 지우는 과정을 통해 소수를 구하는 방법이다. 만약 1~n 사이의 소수를 구하고 싶다면 √n 까지만 구하면 된다. 왜일까? n보다 작거나 같은 합성수 m=ab가 있다고 하자. a와 b가 모두 최대일 때는 a=b=√n 일 때이다. a가 이보다 커지면 b가 √n보다 작아지고 반대의 경우엔 a가 √n보다 작아질 것이다. 그러므로 √n 까지만 체크해도 모든 합성수는 지워진다는 것이다.

 

그렇다면 이제 구현을 할 차례이다. 0과 1은 소수가 아니니 지워주고 2부터 시작한다. 2의 배수를 전부 지워주고, 3의 배수를 전부 지워주고, 4의 배수를 지울 필요는 없다. 왜냐하면 4는 앞서 2의 배수를 지울 때 지워졌기 때문이다. 아무튼 그 다음에 5의 배수를 전부 지우고...이런식으로 √n까지 모든 배수를 지우면 된다.

---

소스코드

 

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

int main() {
	int M, N, line, i, j;

	cin >> M >> N;
	bool* isPrime = new bool[N + 1];
	isPrime[0] = false;
	isPrime[1] = false;
	for (i = 2; i < N + 1; i++)
		isPrime[i] = true;
	line = sqrt(N) + 1; //제곱근까지만 체크
	for (i = 2; i <= line; i++) {
		if (isPrime[i]) {
			for (j = 2 * i; j < N + 1; j += i) //내 다음부터 지우기
				isPrime[j] = false;
		}
	}
	for (i = M; i < N + 1; i++) {
		if (isPrime[i])
			cout << i << '\n';
	}
}