[BOJ] 1929번 소수 구하기

에라토스테네스의 체 구현하기

#include <iostream>
#include <cstdio>
using namespace std;
 
bool is_prime(int n)
{
    for(int i = 2;i<n;i++){
        if(n%i == 0)
            return false;
    }
    return true;
}
void Eratos(int n,int m)
{
    int prime[1000001] = { 1, 1, };
 
    for(int i = 2; i*i <= m; i++){
        if(prime[i] == 0 && is_prime(i)){               // 만약 i가 소수면
            int mul = i;
            for(int j = i + mul; j <= m; j+=mul){           // i의 배수는 소수가 아니다.
                prime[j] = 1;
            }
        }
    }
    for(int i = n; i <= m; i++)
        if(prime[i] == 0)
            printf("%d\n",i);                                       // cout 시간초과
}
 
int main()
{
        int n,m;
        cin >> m >> n;
        if(n==1 && m == n);
        else
            Eratos(m,n);
        return 0;
}