[백준] 1929 (에라토스테네스의 체)

소수찾기문제는 유명한 알고리즘인 에라토스테네스의 체를 이용하면 쉽게풀수있습니다.

에라토스테네스의 체의 최악 수행시간은 O(N*log(logN))이라고합니다.

#include <iostream>
#include <math.h>
using namespace std;

int main() { // 에라토스테네스의 체를 이용한 소수 구하기
	std::ios::sync_with_stdio(false);
	int M, N; // M <= N

	cin >> M >> N;

	bool* arr = new bool[N + 1];

	for (int i = 2; i <= N; ++i) {
		arr[i] = true;
	}

	int sqrt_N = (int)sqrt(N);

	for (int i = 2; i <= sqrt_N; ++i) {
		if (arr[i] == true) {
			for (int j = i; i*j <= N; ++j) {
				arr[i*j] = false;
			}
		}
	}

	for (int i = M; i <= N; ++i) {
		if(arr[i] == true) cout << i << endl;
	}

	return 0;
}