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

문제 링크 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제 풀이

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

#include <iostream>
#include <vector>

using namespace std;

int m, n;
vector<bool> state(1000005, true);

void prime(int n){
  state[1] = false;
  for(int i = 2; i*i <= n; i++){
    if(!state[i]) continue;
    for(int j = i*i; j <= n; j += i)
      state[j] = false;
  }
}

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

    cin >> m >> n;
    prime(n);
    for(int i = m; i <= n; i++){
        if(state[i] == true) cout << i << "\n";
    }
}