[BOJ] 백준 1929번 소수 구하기 풀이

| |
백준 온라인 저지 백준 1929번 - 소수 구하기 C++ 풀이


문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.


입력

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


출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.


풀이

아마 검색을 통해 이 포스트를 들어왔다면 쉬워보이던 문제에 예상치 못하게 시간초과를 맞아 지금 몹시 당황스러울 것이다. 그렇다면 에라토스테네스의 체를 다시 구글에 검색해보기 바란다. 이름은 굉장히 어려워보이지만 사실 중학교 수학 과정에서 배웠던 소수 판정법이다. 해당 판정법은 거의 선형 시간에 비례하여 소수를 판정할 수 있다. 정확하게는 O(nloglogn) 시간복잡도를 갖는다. 아래 코드는 가장 일반적인 약간의 최적화가 들어간 에라토스테네스의 체 구현 코드이다. 요긴하게 써먹으니 어딘가에 저장해두고 적절히 꺼내쓰거나 외우면 좋다.


전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

bool isPrime[1000001];

// 0 부터 n 까지의 소수 판정
void eratos(int n){
    memset(isPrime,1,sizeof(isPrime));
    isPrime[0]=isPrime[1]=false;
    for(int i=2;i<=sqrt(n);i++)
        if(isPrime[i])
            for(int j=i*i;j<=n;j+=i)
                isPrime[j]=false;
}

int main(){
    int M,N; cin>>M>>N;
    eratos(N);

    for(int i=M;i<=N;i++) if(isPrime[i]) cout<<i<<'\n';

    return 0;
}
0%