[백준] 1929번 소수 구하기

문제: 1929번: 소수 구하기

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x12.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
//#include <bits/stdc++.h>

using namespace std;

vector<int> sieve(int m, int n) {
    vector<int> primes;
    vector<bool> state(n + 1, true);
    state[1] = false;

    for (int i = 2; i <= n; i++) {
        if (!state[i]) continue;
        for (int j = 2 * i; j <= n; j += i) {
            state[j] = false;
        }
    }
    for (int i = m; i <= n; i++) {
        if (state[i]) primes.push_back(i);
    }
    return primes;
}

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

    int m, n;
    cin >> m >> n;
    vector<int> answer = sieve(m, n);
    for (int i = 0; i < answer.size(); i++)
        cout << answer[i] << "\n";

    return 0;
}

 

범위가 주어진 경우에 소수를 찾으려면 에라토스테네스의 체를 이용하면 된다.

 

1은 false 로 놓고 시작한다. 2부터 시작 하는데, 자기 자신의 배수들을 for 문을 돌면서 다 false 로 갱신해준다. 그러면 저절로 소수만 남게 된다.

 

마지막에 반환받은 vector 값을 이용해서 출력하면 끝~_~