수학_백준_소수_에라토스테네스의 체

에라토스테네스의 체

범위 안에서 소수를 판별하거나 구할 때 사용한다. 위 코드에서 범위를 주고 for문으로 탐색을 하면 시간복잡도는 O(N x 루트N)이다.

이는 시간이 너무 길어서 위와 같이 풀면 안된다. 따라서 범위라는 조건이 있을 경우에라토스테네스의 체를 이용하자.

1. 2부터 N까지 모든 수를 쓴다.

2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다.

3. 그 수는 소수이다.

4. 이제 그 수의 배수를 모두 지운다.

위의 과정을 반복한다. 언제까지? 끝까지는 시간이 너무 오래 걸린다. 그런데 에라토스테네스의체에서 중요한 성질이 있다. 이는 어떤 수의 제곱수 이전은 이미 지워졌다. 즉 N이 100일 경우 검사는 2, 3, 5, 7 까지만 하고 11부터는 할 필요가 없다. 이는 11의 제곱 즉 121까지 모두 이미 지워져있다.

시간복잡도는 O(N x Log(LogN))이다. 대략 O(N)이다.

구현

1부터 N까지 모든 소수를 구하는 것이 목표이기 때문에, 구현할 때는 바깥 for문 (i)를 N까지 돌린다.

안쪽 for문 (j)는 N의 크기에 따라서, i*i 또는 i*2로 바꾸는 것이 좋다.

i가 백만인 경우 i*i는 데이터 크기를 넘어가기 때문이다. 따라서 이 경우는 i*2로 사용해야 된다. 즉 정수 오버플로우를 막기 위해서 필요하다.

www.acmicpc.net/problem/1929

#include <iostream>
using namespace std;
 
int main() {
    bool a[1000000];
    int min, max;
    cin >> min >> max;
    bool * value = new bool[max + 1];// true if it is deleted
    for (int i = 0; i <= max; i++) {
        value[i] = false;
    }
    //Initialize
 
    for (int i = 2; i <= max; i++) {
        if (value[i] == false) { // Not deleted
            if (i >= min) {
                printf("%d\n", i);
            }
            for (int j = i * 2; j <= max; j += i) { //use i*2 to protect Overflow 
                value[j] = true;
            }
        }
    }
}