[BOJ] 1929 :: 소수 구하기 (에라토스테네스의 체 구현)

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

a와 b사이의 모든 소수를 구해서 출력하는 문제입니다.

너무 뻘짓을 많이 해서 이것때매 정답률 엄청 낮아짐 ㅠㅠ속상하다

소수를 구하는데 우리가 일반적으로 생각하는 그 평범한 포문을 쓰면 시간초과가 납니다(1부터 자기 자신 전까지의 수로 나눠지는지 아닌지 판단하는 과정)

가장 효율적인 소수를 구하는 방법인 '에라토스테네스의 체'를 사용해야 합니다.

이 방법은 큰 배열을 잡아놓고 2부터 n까지 자신의 배수를 지워나가는 방법입니다.

이미 지워진 부분이라면 검사할 필요가 없고 지워지지 않았다면 자기 자신의 배수를 지워주면 됩니다.

주의해야 할 점

1. i*i가 n보다 작을 때 까지만 확인해야 합니다. 소수의 특성상 구하고자 하는 수의 루트값보다 작은 값은 소수가 될 수 없으니까요!

2. 배수를 지워나갈 때 자기 자신은 지우면 안되고 자기 자신 *2부터 지워야 합니다. 예를들어 6은 소수가 아니지만 3은 소수이니까!

3. 이 문제에서 endl을 많이 쓰게 되는데 이부분에서 시간이 엄청 걸린다고 합니다. 얘 때문에 시간초과 엄청 났네요 ㅠ 

'/n'을 쓰거나 std::ios::sync_with_studio(false), 또는 cin.tie(NULL)이거 써주시면 됩니다.

#include <iostream>
#include <vector>
using namespace std;
int prime[1000001];
bool check[1000001];
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	int m, n;
	cin >> m >> n;
	check[0] = true, check[1] = true;
	for (int i = 2; i*i <= n; i++)
	{
		if (check[i] == false)
		{
			for (int j = i * 2; j <= n; j += i)
			{
				check[j] = true;
			}
		}
		
	}
	for (int i = m; i<= n; i++)
	{
		if (check[i] == false)
		{
			cout << i << '\n';
			
		}
	}
}