[C++] 백준 1929번 소수 구하기

에라토스테네스 체를 이용해서 구하는 문제

처음에는 쉽게 소수 구하는 알고리즘을 적용했는데

(앞 수랑 비교하는거)

이러다보니 시간 초과가 발생했다.

아무래도 효율적인 알고리즘을 찾다가,

결국 구글에 검색을 해보니 에라토스테네스의 체라는 알고리즘이 있었다.

다른분들의 코드를 참고해서 작성했다.

 

#include <iostream>
#include <cmath>
using namespace std;

bool primeArr[1000001];

int main(void) {

	int m, n;
	cin >> m >> n;
	for (int i = m; i <= n; i++) {
		primeArr[i] = true;
	}
	
	primeArr[1] = false;
	for (int i = 2; i <= sqrt(n); i++) {
		for (int j = i + i; j <= n; j += i) {
			primeArr[j] = false;
		}
	}
	
	for (int i = m; i <= n; i++) {
		if (primeArr[i]) printf("%d\n", i);
	}
}