[백준]1929-소수 구하기

이 문제는 아래의 "알고리즘 분류"에 힌트가 있다.

 

에라토스테네스의 체.

 

간단히 설명하면, 2를 제외한 2의 배수를 소수의 후보에서 제외하고, 3을 제외한 3의 배수를 소수의 후보에서 제외, (4는 후보에서 제외되었으니 5를 제외한 5의 배수를 소수의 후보에서 제외.. 와 같은 식으로 원하는 범위까지의 소수를 구하는 방법이다.

 

근데 만약 100까지의 소수를 구한다고 가정하면, 굳이 2부터 100까지 1씩 늘려가며 모두 배수를 검사할 필요가 없다.

100의 절반인 50부터는 검사를 하나마나 남아있는 후보들의 배수는 범위 안에 없기 때문이다.

그러므로 최대 범위의 절반까지 배수를 구하면서 후보를 제외한다.

 

아래가 그 코드이다.

//#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
//#include <iostream>
//using namespace std;
 
int main()
{
    int min, max;
    //cin >> min >> max;
    scanf("%d %d", &min, &max);
 
    bool* ary = new bool[max + 1]{ false };
    ary[1] = true;
    for (int i = 2; i <= max / 2; i++) {
        if (!ary[i]) {
            for (int j = 2; j * i <= max; j++) {
                ary[i * j] = true;
            }
        }
    }
    for (int i = min; i <= max; i++)
        if (!ary[i])
            printf("%d\n", i);
            //cout << i << endl;
}

 

cout/cin으로 했더니 또 아쉽게 시간초과가 떴다.

흐음...

 

아 맞다 bool배열을 동적할당하고 초기화할 때 한 바퀴를 돌리기에는 시간이 아까워서 그냥 {false}로 전체 초기화했다. {true}로 했었는데 0번째만 true로 되더라.. 그래서 소수를 false로 하기로 했다..