알고리즘/알고리즘 문제 풀이

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

용꿀 2023. 5. 15. 01:39

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

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

www.acmicpc.net

문제 풀이

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

#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";
    }
}