[백준 #1929] 소수 구하기(에라토스테네스의 체)(C++)

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

1929번: 소수 구하기

#include <iostream>
#include <vector>

using namespace std;
int main()
{
	int m, n;
	cin >> m >> n;

	vector<int>check(n+1, 1);
	check[1] = 0;//1은 소수가 아니다.
	for (int i = 2; i * i <= n; i++)
	{
		if (check[i])
		{
			for (int j = 2 * i; j <= n; j += i)
			{
				if (check[j])
					check[j] = 0;
			}
		}
	}
	for (int i = m; i <= n; i++)
	{
		if (check[i])
			cout << i << "\n";
	}

}

이 문제는 에라토스테네스의 체를 사용해야 한다.

출처 : https://ko.wikipedia.org/wiki/에라토스테네스의_체

 

2부터 n까지의 배열이 있다면,

i=2부터 해서 i를 1씩 늘려가며 i의 배수들을 지워주는 것이다. 언제까지? i*i<=n까지!

i의 배수들을 지우고 있기 때문에, i<=n까지 갈 필요가 없다.

 

초기에 check 벡터를 1로 세팅하고, 배수에 해당하는 수는 0으로 세팅하였다.

1은 소수가 아니므로 0으로 세팅하여야 한다.

 

check=1로 살아남은 수는 소수! 출력하면 된다.