1929_소수구하기

#include <iostream>
using namespace std;

void EratosthenesSieve(int a, int b) {
	bool check[1000001] = { 0, };
	check[0] = 1; check[1] = 1;
	for (int i = 2; i*i <= b; i++) {
		if (check[i] == false) {
			for (int j = i * i;j <= b;j += i) {
				check[j] = true;
			}
		}
	}
	for (int i = a; i <= b; i++) {
		if (check[i] == false) cout << i << '\n';
	}
}

int main() {
	int m, n;
	cin >> m >> n;
	EratosthenesSieve(m, n);
}

해당 문제는 에라토스테네스의 체를 알면 쉽게 풀 수 있다.
에라토스테네스의 체는 다음 글을 참고.

https://velog.io/@kimeunseo58/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98-%EC%B2%B4