에라토스테네스의 체

에라토스테네스의 체 : 소수를 빠르게 구해낼 수 있는 알고리즘

 

2가지의 알고리즘이 있다.

 

1000 이하의 소수를 찾아내보자

 

1. 반복문을 통해 약수를 걸러내는 방법을 이용한 알고리즘

#include <iostream>
#include <vector>
using namespace std;
bool check[1000];
vector<int> v;
int main() {
    for (int i = 2; i <= 1000; i++)
        check[i] = true; // 전부 소수로 통일
    // 제곱근까지만 확인해주면 된다.
    for (int i = 2; i*i <= 1000; i++) {
        if (!check[i]) continue;
        // i 번째 값은 이미 소수. i*i 부터 i씩 더해가면서 약수가 되는 값을 걸러낸다.
        for (int k = i * i; k <= 1000; k += i) {
            check[k] = false;
        }
    }
    for (int i = 2; i <= 1000; i++) {
        if (check[i]) // true 이면 소수
            v.push_back(i);
    }
}

 

2. 소수는 소수로 나누어 떨어지지 않는다는 방법을 이용한 알고리즘

#include <iostream>
#include <vector>
using namespace std;
 
bool check[1000];
vector<int> v;
 
int main() {
    // 벡터 v는 소수값만을 저장
    // 2는 소수라는 것을 초기값으로 시작
    v.push_back(2);
 
    for (int i = 3; i <= 1000; i++) {
        // t 는 소수임을 확인
        bool t = true;
 
        // 현재 i 가 벡터값으로 나누어 떨어진다면 약수가 되므로 소수가 아님
        for (int k = 0; k < v.size(); k++) {
            if (i%v[k] == 0) {
                t = false;
                break;
            }
            // 소수는 제곱근 초과의 수로 나누어볼 필요가 없다
            if (v[k] * v[k] > 1000) break;
        }
        // 소수이면 벡터에 저장
        if (t == true) v.push_back(i);
    }
}

 

소수의 범위가 클수록 2번의 방법은 각 숫자마다 벡터에 담긴 소수를 통해 약수를 확인해야하므로 비효율적이다.

==> 범위가 클수록 1번의 약수를 거르는 방법을 이용한다.

 

어떤 방법이든 소수에 관한 문제를 풀 때 가장 중요한 요점은

임의의 소수는 제곱근보다 큰 수로는 나누어 떨어지지 않는다는 것이다.

이것만 기억해둬도 시간해결에 큰 영향을 미치게 될 것이다.

 

관련 풀어본 백준 문제들 :

셀프 넘버 - https://www.acmicpc.net/problem/4673

소수 찾기 - https://www.acmicpc.net/problem/1978

소수 구하기 - https://www.acmicpc.net/problem/1929

베르트랑 공준 - https://www.acmicpc.net/problem/4948

골드바흐의 추측 - https://www.acmicpc.net/problem/9020

소수의 연속합 - https://www.acmicpc.net/problem/1644

제곱 ㄴㄴ 수 - https://www.acmicpc.net/problem/1016