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

 문제 설명 

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

 

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

 풀이 

평범한 소수 구하기라면 그냥 2중 반복문을 통해서 풀이를 진행하면 되지만 시간제한이 2초로 굉장히 짧은 시간내에 풀이를 진행해야하기 때문에 특별한 알고리즘을 사용해야합니다.

 

바로 '에라토스테네스의 체'입니다. 소수를 빠르게 판별해나가는 알고리즘입니다.

 

이런 알고리즘의 존재를 처음 알았던 저로써는 일단 알고리즘을 공부해나가는 것 부터 시작했습니다.

일단 글로 간단히 설명하자면 소수를 2부터 하나씩 찾아나가면서 2를 찾으면 2의배수를 3을 찾으면 3의 배수를 다 배제 시키면서 탐색을 진행하는 것입니다. 그렇게 되면 4는 2의 배수이기 때문에 배제되고 5는 앞의 수 중 누구의 배수도 아니기 때문에 5의수를 배제시키고 이런식으로 탐색을 진행하는 것입니다.

 

위키의 에서 가져온 GIF인데 아주 보기쉽게 잘 설명되어있습니다. 이런식으로 발견하는 소수의 배수를 모두 배제 시킴으로써 소수만을 구하는 알고리즘입니다.

 

그리고 이 풀이에 있어서 더 눈여겨 봐야하는 부분은 자신의 소수를 처음으로 찾는 구간은 자신의 2제곱 부터 입니다.

 

2이라면 4, 3이라면 9, 5라면 25에서부터 숫자들이 배제되는 것을 볼 수 있습니다. 이렇게 되면 또 다시 탐색할 숫자가 줄어듭니다. 그러니 자신의 제곱보다 작은 숫자들을 배제를 시키고 시작을 하면 됩니다.

 코드 

#include <string>
#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <cmath>

using namespace std;

int main(void) {
    int a, b;
    scanf("%d %d", &a, &b);

    bool* check = new bool[b + 1];

    for (int i = 0; i < b + 1; i++) {
        check[i] = true;
    }

    int j;

    for (int i = 2; i < b + 1; i++) {
        if (check[i] == true) {
            if ((unsigned int)pow(i, 2) > 1000001) {
                break;
            }
            else {
                for (j = (int)pow(i, 2); j < b + 1; j += i) {
                    check[j] = false;
                }
            }
        }
    }

    if (a == 1) a = 2;

    for (int i = a; i < b + 1; i++) {
        if (check[i] == true && i >= a) printf("%d\n", i);
    }

    delete []check;
    return 0;
}

 

※더 좋은 방법과 알고리즘 혹은 개선해야할 부분은 댓글로 적어주시면 감사하겠습니다.