<백준> 1929

소수 구하기

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

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

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

에라토스테네스의 체 공식을 사용해서 문제를 해결하면 된다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int m,n;
	cin >>m>> n;

	vector<bool> v(n + 1, true);
	v[0] = false;
	v[1] = false;

	for (int i = 2; i * i <= n; i++)
	{
		if (v[i])
		{
			for (int j = i * i; j <= n; j += i)
			{
				v[j] = false;
			}
		}
	}

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