[C++] 1929: 소수 구하기 - 에라토스테네스의 체에서 제곱근까지 판별하는 이유

문제

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

입력

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

출력

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

풀이

기초적인 에라토스테네스의 체 문제 !

소수는 자기 자신과 1만을 약수로 가지는 수이다.
그러므로 ++n을 최대 수까지 곱하면서 해당하는 수를 제외해주면 소수만이 남는다.

이 때 n은 판정하려는 소수의 루트값보다 작은 정수까지만 계산해도 된다. 그 이유는 다음과 같다.

어떤 수 x가 소수인지 판정하려면, 1과 x를 제외한 수 중에서 x의 약수가 되는 수를 찾아야 한다.
따라서 x = i * j로 표현할 수 있다.
에라토스테네스의 체 알고리즘에서, i와 j의 역할을 확인할 수 있다.

이해를 돕기 위해 26까지 소수를 판별하는 예시를 들어보자.

1. i는 2에서 시작한다. 2에 2, 3, 4...를 곱하여 최대값 26까지 판별한다. 이 과정에서 4, 6, 8, 10, ... 26까지 판별될 것이다.
2. 다음엔 i에 1을 더해 3에서 판별한다. 3에 2, 3, 4..를 곱하여 최대값 26보다 작은 24까지 판별한다. 이 과정에서 6, 9, 12, ... 24까지 판별될 것이다.
3. 위 과정을 반복한다.

아래는 이 과정을 표로 나타낸 그림이다.

우리는 26의 제곱근인 5.xxx 이하까지 판별할 것이므로, i가 5가 되는 시점까지만 판별한다.
만약 여기서 26의 제곱근을 넘어 i = 6부터 더 판별한다고 하자.

i는 6에서 시작하여 12, 18, 24를 판별할 것이다. 하지만 이 과정은 의미가 없다.

이미 앞의 과정에서 n의 제곱근보다 큰 i의 배수는 모두 판별하였다. i = 6에서 12, 18, 24를 판별하는 부분인 초록색 부분을 보면, 이미 제곱근 이하의 i에서 초록 부분이 모두 판별된 것을 볼 수 있다. 뒤의 파랑, 보라 부분도 마찬가지이다.

따라서, x >= a * a를 만족하는 정수 a의 최대값의 배수까지만 판정하면, (즉 x의 제곱근까지만 판정하면) x까지의 모든 소수를 판정할 수 있다.

코드

#include <iostream>

using namespace std;

void eratos(void);

int m, n;
int isnt_prime[1000001] = {1, 1};

int main(void)
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	eratos();

	return (0);
}

void eratos(void)
{
	cin >> m >> n;

	int i = 1;
	while (++i <= 1000)
	{
		int j = 1;
		while ((++j) * i <= 1000000)
			isnt_prime[i * j] = 1;
	}

	i = m - 1;
	while (++i <= n)
		if (isnt_prime[i] == 0)
			cout << i << '\n';

	return ;
}

성공 !