백준 1929번 cpp로 풀기

1929번 문제는 M이상 N이하의 소수를 빠르게 찾고 출력하는 문제이다.

이 문제는 에라토스테네스의 체 알고리즘을 이용하여 풀 수 있다.
먼저, vector<bool> isPrime(N+1,true)를 생성하여 모든 수를 소수로 가정한다.
그리고 2부터 N까지 배수를 제거하여 소수만 남기는 구조이다.
코드는 아래에 적어두었다.

ios::sync_with_stdio(false);와 cin.tie(nullptr);는 c++에서 입출력 성능을 최적화 하기 위한 코드이다.
1️⃣ios::sync_with_stdio(false);

• c++의 표준 입출력인 cin,cout과 c의 표준 입출력인 scanf,printf의 동기화를 해제하는 역할을 한다.
• 기존적으로 c++의 cin,cout은 c의 scanf,printf와 동기화되어 같이 사용될 때 정상적으로 동작하도록 보장된다.
• 하지만 동기화과정이 불필요한 경우 성능을 향상시킬 수 있다.
• 즉, sacnf,printf를 사용해야한다면 이 옵션은 쓰면 안된다.
  2️⃣cin.tie(nullptr);
• 기본적으로 cin과 cout은 연결(tie)되어있다.
• 즉, cin이 사용될 때마다 자동으로 cout이 flush(출력 버퍼 비움)이 되어 즉시 출력된다.
  이를 해제(nullptr로 설정)하려면 불필요한 flush를 방지하여 입출력 속도를 높일 수 있다.

#include<iostream>
#include<vector>

using namespace std;

void sieve(int M, int N) {
    vector<bool> isPrime(N+1, true);
    isPrime[0] = isPrime[1] = false;

    //에라토스테네스의 체 알고리즘
    for(int i = 2; i*i <=N; i++){
        if(isPrime[i]){
            for(int j = i * i; j<= N; j+=i){
                isPrime[j] = false;
            }
        }
    }

    //결과 출력
    for(int i = M; i<=N; i++){
        if(isPrime[i]){
            cout<<i<<'\n';
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int M, N;
    cin >> M >> N;
    sieve(M, N);

    return 0;
}