[백준/C++] 1929번 소수 구하기

문제: www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

문제풀이

 

처음 문제를 풀 땐 브루트 포스로 문제를 풀었다.

하지만 범위가 1 ≤ M ≤ N ≤ 1,000,000 으로 큰 숫자여서 시간 초과가 나왔다.

 

이 문제는 "에라토스테네스의 체" 라는 알고리즘으로 풀어야 한다.

 

입력 범위만큼 배열을 선언하고

숫자 2부터 해당 숫자를 제외한 배수를 인덱스로 가지고 있는 배열을 1로 초기화한다.

 

배열 크기만큼 반복한 후 배열에 0이 있으면 해당 배열의 인덱스를 출력한다.

이때, 숫자 1은 소수가 아니므로 arr[1]은 1로 따로 초기화시켜주어야 한다.

 

에라토스테네스의 체, 위키백과

코드

#include <iostream>

using namespace std;

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

    int M,N;
    cin>>M>>N;

    int arr[N+1]={0,}; //N+1 크기의 배열 선언
    arr[1] = 1; //1은 소수이므로 1로 초기화 해준다.
    for(int i=2; i<=N; i++){ //숫자 2부터
        for(int j=2; i*j<=N; j++){
            arr[i*j] = 1; //i의 j배수 이므로 소수가 아니다. -> 1로 초기화
        }
    }


    for(int i=M; i<=N; i++){
        if(arr[i] == 0) //0이면 출력
            cout<<i<<"\n";
    }

    return 0;
}

 

 

결과