BOJ 백준 1929 : 소수 구하기

시작하면서

　이번 문제는 소수 구하기 문제이다.

BOJ 1929 - 소수 구하기

​

문제 이해

해당 문제는 소수를 구하는 알고리즘인 에라토스테네스의 체를 사용해서 해결하는 문제이다. 최대 숫자 N까지의 소수를 구하는 알고리즘 순서는 다음과 같다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수의 범위를 배열로 만든다.
2. 2는 소수이므로 true 값을 넣어준다.
3. 자기 자신을 제외한 2의 배수를 모두 false 값을 넣어준다.
4. 자기 자신을 제외한 3의 배수를 모두 false 값을 넣어준다.
5. 3/4번을 숫자 2,3,…,sqrt(N)의 범위까지 반복한다. (sqrt(N) 포함)
6. 배열의 값이 true인 숫자들만이 소수이다.

5번에서 sqrt(N)까지만 하는 이유는 수학자들이 증명했는데, 단순히 생각해보아도 3^2 = 9의 배수들은 3으로 이미 나누었으니 두 번 계산할 필요가 없고, 5^2 = 25의 배수들은 이미 5로 나누었으니 두 번 계산할 필요가 없으므로 루트로 범위를 좁혀서 계산량을 줄인다.

​

해결

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

void MakePrimeNumberVector(vector<bool>& v, int N)
{
	int length = sqrt(N);

	v[0] = false;
	v[1] = false;

	for (int i = 2; i <= length; i++)
	{
		for (int j = i + i; j <= N; j += i)
		{
			v[j] = false;
		}
	}
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<bool> v;
	int N, M;

	cin >> M >> N;

	v.resize(N + 1, true);

	MakePrimeNumberVector(v, N);

	for (int i = M; i <= N; i++)
	{
		if (v[i] == true)
		{
			cout << i << "\n";
		}
	}

	return 0;
}

​

마치며

　잊을만하면 생각나는 소수 구하기 알고리즘!