[알고리즘] 소수의 개수 찾기 - 에라토스테네스의 채

n부터 m까지 소수의 갯수를 구하는데 빠르게 구하는 방법

2부터 각 범위까지 배수를 지워 가는 형식

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
bool pn[1000001] = {0};
 
 
 
int main()
{
 
    int n, m ;
    std::fill_n(pn, 1000001, true);
 
    cin >> n >> m;
 
    if(n <1 && n > 1000000) return -1;
    if (m <1 && m > 1000000) return -1;
    
    for(int i = 2; i*i <= m ;i++ ){
        for(int a = 1 ; i*a <=m ; a++){
            
            if(pn[i*a] == false) continue;
            
            if(pn[i*a] && a == 1){
                pn[i*a] = true;
            }
            else {
                pn[i*a] = false;
            }
        }
    }
 
    for(int i = n ; i <= m;i++)
    {
        if (i == 1) continue;
        if(pn[i]) cout << i << '\n';
    }
 
}