[#1929] 소수 구하기

#include <iostream>
#include <vector>
#include <math.h>
 
using namespace std;
 
int main() {
    int m, n;
    cin >> m >> n;
 
    vector<bool> isPrime(1000001, true);
 
    isPrime[1] = false; //1은 소수 아님
 
    for (int i = 2; i <= (int)sqrt(n); i++) {
        if (isPrime[i]) {
            for (int j = i + i; j < 1000001; j = j + i) {
                isPrime[j] = false;
            }
        }
    }
 
    for (int i = m; i <= n; i++) {
        if (isPrime[i])
            cout << i << "\n";
    }
 
    return 0;
}

 

처음에는 모든 수에 대해 sqrt(n)으 나눠보는 방법으로 소수 판별하다가 시간 초과 떠서 에라토스테네스의 채 사용

2부터 sqrt(n)까지 소수이면 배수 다 지우기

 

많은 수에 대해 소수 판별해야할때는 에라토스테네스의 채를 쓰자