Codility Lesson11 - CountSemiprimes

🔍 문제

---

 

주어진 범위내에서 두 소수의 곱의 값인 semiprime의 개수를 구하는 문제이다.

CountSemiprimes coding task - Learn to Code - Codility

 

✏️ 풀이 - JS

---

 

Lesson의 소제목이 Sieve of Eratosthenes(에라토스테네스의 채)이길래 이 이론에 대해서도 정리해보았다.

 

링크로 가기 👉 Sieve of Eratosthenes(에라토스테네스의 채)에 대해서 알아보자.

 

로직은 아래와 같으며, 시간 복잡도는 O(N * log(log(N)) + M) 가 나왔다.

1. 1~N 까지의 인덱스를 가진 배열을 만들어준 후, 인덱스를 기준으로 소수라면 값을 0을 넣어주고, 소수의 배수라면 해당하는 소수를 값으로 넣어주었다.
2. 소수의 개수를 가진 배열을 만들어준다. 이 배열에는 1번에서 만들어두었던 배열을 활용해서 s[i]/i를 한 후 s[s[i]/i]가 소수인지 확인한다.(소수라면 값이 0이다.) 소수인 경우 sum++을 해준다.
3. 마지막으로 배열 P와 Q의 범위를 확인해서 semiCnt배열에서 개수를 확인 해준다.

function getArray(N) { // 빈배열 만드는 함수
    let arr = [];

    for(let i = 0; i < N; i++){
        arr.push(0);
    }

    return arr;
}

function solution(N, P, Q) { 
    const size = P.length;
    let result = P.map(i => 0);

    let s = getArray(N + 1);
    let i = 2;

    while( i * i <= N) { //1~N까지의 범위의 수를 소수와 소수의 배수로 구분함
        if(s[i] === 0) {
            let j = i * i;
            while(j <= N) {
                if(s[j] === 0) {
                    s[j] = i;
                }

                j+=i;
            }
        }
        i++;
    }


    let semiCnt = getArray(N + 1);
    let sum = 0;

    for(let i = 1; i <= N; i++){ // 해당 수가 소수*소수의 수인지 확인 후, 
    					//i수까지의 semiprime 개수를 값으로 넣어준다.
        if(s[i] != 0) {
            let j = i / s[i];
            if(s[j] === 0) {
                sum++;
            }
        }
        semiCnt[i] = sum;
    }

    for(let i = 0; i < P.length; i++) {
        let q = Q[i];
        let p = P[i];

        result[i] = semiCnt[q] - semiCnt[p-1];
    }

    return result;

}