BOJ - 소수 구하기(1929)

실버2 : 수학 문제이다.

생각

소수 구하는 알고리즘인 에라토스테네스의 체를 사용하면 간단히 풀 수 있다.

Code

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define MAX 1000000
using namespace std;
bool isPrime[MAX+1];
int N, M;
 
void SeiveofEratosThenes(){
    fill(isPrime+2, isPrime+N+1, true);
    for (int i = 2; i*i <= N; i++) {
        if (isPrime[i] == false) continue;
        for (int j = i*i; j <= N; j+=i) {
            isPrime[j] = false;
        }
    }
}
 
 
int main(){
    cin >> M >> N;
    SeiveofEratosThenes();
    for (int i = M; i <= N; i++) {
        if (isPrime[i] == true) cout << i << '\n';
    }
    return 0;
}
 

Reference

• 백준(1929번) - 소수 구하기