[BOJ]1929 - 소수 구하기

1929

전체코드

#include <iostream>
using namespace std;

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

	int n{ 0 };
	int m{ 0 };

	cin >> m >> n;

	
	bool* isPrime = new bool[n + 1];

	for (int i = 2; i <= n; i++)
		isPrime[i] = true;

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

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

	delete[] isPrime;
}

while 문으로 하나씩 소수를 구하려고 했는데 시간 초과!
알고리즘 분류란을 열어보니 에라토스테네스의 체가 있었다.
이를 구글링하니 위키피디아에 c++ 코드가 그대로!

바로 가져다 쓰니 통과!

찝찝하지만 몰랐으면 절대 못 풀었을 듯. 처음 보는 개념이었다 ㅎㅎ..

---

참고자료

에라토스테네스의 체