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

1. 속도 개선 아이디어

 

CountSemiPrimes #2에서는 소수 판별 알고리즘과 semi prime 계산하는 부분을 수정했는데, 생각보다 성능 개선이 미비했다. (결과를 비교해보면, 아주 쪼금 좋아지긴 했다)

 

이제 개선해야할 코드로는, semi prime 개수 세는 부분만이 남아있다.

 

semi prime 개수 세는 코드는 현재 이중반복문으로 되어있는데, 

prefix sum을 이용하면, 즉시 계산할 수 있다. 

 

 

2. 코드 (C++)

semi prime도 값을 직접 다루지 않고, table에 표시해두는 형태로 수정했다.

 

 

#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(N + 1, 0);
    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[i] = 1;
    }

    //prefix sum of semi_primes
    vector<int> prefix_sum(N + 2, 0);
    for(size_t i = 1; i < prefix_sum.size(); i++)
    {
        prefix_sum[i] = prefix_sum[i - 1] + semi_primes[i - 1];
    }

    //[P..Q] 범위안에 있는 semi prime number 개수 세기
    vector<int> result = {};
    for(size_t K = 0; K < P.size(); K++)
    {
        int from = P[K];
        int to = Q[K] + 1;
        result.emplace_back(prefix_sum[to] - prefix_sum[from]);
    }
    
    return result;
}

 

 

3. 결과