Lesson 11. Sieve of Eratosthenes - CountSemiPrimes #2 (속도 개선-1)

1. 속도 개선 아이디어

CountSemiPrimes #1에서 사용하고 있는 소수 판별 알고리즘은 좋은 알고리즘이긴 하지만, 특정한 숫자가 소수인지 판별하는데 적합한 알고리즘이다. 

게다가, semi prime을 구할 때, 소수를 하나 하나씩 곱해가며, 계산하고 있다.

 

'에라토스테네스의 체'를 이용하면, 특정 범위안에 있는 소수를 모두 찾을 수 있고, semi prime 계산 속도도 증가시킬 수 있다.

 

아라토스테네스의 체에 대한 내용을 아래 링크를 참조 바란다.

에라토스테네스의 체 이론

에라토스테네스의 체 구현(C++)

---

 

semi prime 설명을 잘 생각해보면, semi prime은 합성수 임을 알 수 있다.

정확히는 합성수 중에서, 소인수만을 인수로 갖는 합성수이다.

 

아라토스테네스의 체를 응용하면,  합성수에 대한 최소 소인수를 찾을 수 있다.

이를 이용해 semi prime 계산 속도를 증가시켜 본다.

 

2. 문제풀이 전략 

예시) N = 26

 

1) 아라토스테네스의 체를 이용해서 소수를 구한다

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	26

 

2) 아라토스테네스의 체를 이용해서 합성수(N)의 최소 소인수(A)를 구한다

N	1	2	3	4	5	6	7	8	9	10
A	0	0	0	2	0	2	0	2	3	2

N	11	12	13	14	15	16	17	18	19	20
A	0	2	0	2	3	2	0	2	0	2

N	21	22	23	24	25	26
A	3	2	0	2	5	2

 

3) 합성수(N)의 최소 소인수(A)를 이용해 semi prime을 구한다

A = 0, 합성수가 아니다

A ≠ 0, 합성수이다 → (N / A) 를 계산한다 → (N / A)의 값이 소수이다 = semi prime이다

 

4) [P..Q] 범위의 semi prime 개수를 센다

 

3. 코드 (C++)

#include <algorithm>

vector<int> solution(int N, vector<int> &P, vector<int> &Q) {

    //소수 및 최소 소인수 구하기
    vector<int> prime_factors(N + 1, 0);
    vector<int> prime_numbers(N + 1, 1);
    prime_numbers[0] = prime_numbers[1] = 0;
    for(int i = 2; i * i <= N; i++)
    {
        if(prime_numbers[i] == 1)
        {
            int k = i * i;
            while(k <= N)
            {
                prime_numbers[k] = 0;
                if(prime_factors[i] == 0) prime_factors[k] = i;
                k += i;
            }
        }
    }

    //semi prime number 구하기
    vector<int> semi_primes = {};
    for(int i = 0; i < static_cast<int>(prime_factors.size()); i++)
    {
        if(prime_factors[i] == 0) continue;

        int a = prime_factors[i];
        int b = i / a;
        if(prime_numbers[b] == 1) semi_primes.emplace_back(i);
    }

    //[P..Q] 범위안에 있는 semi prime number 개수 세기
    vector<int> result = {};
    for(size_t K = 0; K < P.size(); K++)
    {
        int cnt = 0;
        for(size_t i = 0; i < semi_primes.size(); i++)
        {
            if(semi_primes[i] > Q[K]) break;
            if(semi_primes[i] < P[K]) continue;
            cnt++;
        }

        result.emplace_back(cnt);
    }

    return result;
}

 

4. 결과

개선 효과가 크지 않다