[백준] 1929번: 소수 구하기

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

문제

반례

1 4
> 2
> 3

1의 경우를 조심하자

알고리즘 접근 방법

에라토스테네스의 체

대표적인 소수 판별 알고리즘이다.
대량의 소수를 한꺼번에 판별하고자 할 때 사용한다.

1. 소수를 판별할 범위만큼 배열을 할당해 그 인덱스에 해당하는 값을 넣어준다.

2. 2부터 시작해서 자기 자신을 제외한 배수들을 지워나간다.

3. 이미 지워진 숫자의 경우 건너뛴다.

1. 1~n까지 각 숫자가 소수인지 아닌지를 나타내는
   bool isPrime[1000000] 선언

2. n까지 에라토스테네스를 수행

3. m ~ n까지 isPrime 배열을 순회하면서 소수이면 출력

풀이

#include <iostream>
using namespace std;


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

    int M, N;

    cin >> M >> N;

    bool arr[1000001] = {false};

    for (int i=2; i<=N; i++){
        if (arr[i] == true) 
            continue;
        for(int j=2*i; j<=N; j+=i){
            if(arr[j] == false){
                arr[j] = true;
            }
        }
    }

    for(int i=M; i<=N; i++){
        if (!arr[i] && i!=1)
            cout << i << '\n';
    }
    return 0;
}

정리

똑똑하군..
90퍼대서 틀려서 봤더니 1의 경우를 놓쳤었다!

💡 참고 포스팅

22. 에라토스테네스의 체
90퍼센트쯤에서 틀렸다고 하네요