[BOJ] 1929 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

에라토스테네스의 체

 

---------------------------------------------------풀이----------------------------------------------------

 

arr[]에서 2부터 N까지의 수에 대해,

자기 자신을 제외한 모든 배수를 true로 바꿔준다.

M부터 N까지 모든 수를 출력한다.

이때, 소수는 2부터 가능하므로, 1이 나올 경우에 대비해

max(M, 2)부터 N까지 출력한다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main(void){
    FASTIO;
    int M, N;
    cin >> M >> N;
    bool arr[1'000'001] = {false, };
    for(int i = 2; i <= N; i++){
        for(int j = i+i; j <= N; j += i){
            arr[j] = true;
        }
    }
    for(int i = max(M,2); i <= N; i++){
        if(!arr[i]){
            cout << i << "\n";
        }
    }
    return 0;
}

---------------------------------------------------후기----------------------------------------------------

 

M이 1이 될 수 있다는 사실을 놓쳐 한 번 틀렸었다.

쉽더라도 문제를 꼼꼼히 읽자!

M부터 N까지 각각 소수인지 판별하는 방식도 있겠지만, 그 방식보다는

N이 1'000'000까지 커질 수 있으므로 에라토스테네스의 체 방식이 좋다고 생각한다.