[백준 1929] 소수 구하기

에라토스테네스의 체를 사용한 문제풀이이다.

 

합성수의 가장 작은 소인수는 반드시 √N 이하임을 사용하였다.

 

---

#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>

#define SIZE 1000001

using namespace std;

int M, N;
vector<int> primes;

void solve()
{
    // primeCheck 배열 모두 1로 초기화해주기
    bitset<SIZE> primeCheck;
    primeCheck.set();

    primeCheck[0] = 0;
    primeCheck[1] = 0;

    // 합성수의 가장 작은 소인수는 반드시 √N 이하이다.
    for (int i = 2; i <= sqrt(N); i++)
    {
        if (primeCheck[i])
        {
            for (int k = 2 * i; k <= N; k += i)
            {
                primeCheck[k] = 0;
            }
        }
    }

    for (int i = M; i <= N; i++)
    {
        if (primeCheck[i])
        {
            primes.push_back(i);
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> M >> N;

    solve();

    for (int i = 0; i < primes.size(); i++)
    {
        cout << primes[i] << "\n";
    }

    return 0;
}