[BOJ 1016] 제곱 ㄴㄴ수

BOJ 1016

문제

풀이

주어진 [min, max] 범위에 대해서 범위 내 임의의 정수 X가 1보다 큰 제곱수로 나누어 떨어지는 지 확인하고 그 갯수를 반환하면 된다.
min의 범위가 1조로 매우 크지만 max가 최대 min + 1백만이므로 범위내 수는 많아도 약 1백만개이다.
임의의 정수 X가 나누어 떨어질 수 있는 최대의 제곱수는 Math.sqrt(X)이므로, [2, Math.floor(Math.sqrt(max))] 범위의 모든 정수의 제곱에 대해 해당 수가 나누어 떨어지는지 확인하면 된다. 이 경우 최대 1백만 개의 숫자에 대해 10만 번의 확인이 필요하므로 1천억 번의 연산이 발생해 시간초과가 예상된다.
이를 줄이기 위해 각 수의 제곱을 확인해보면, 정수 2, 3, 4, 5, 6, 7, 8, 9의 제곱은 각각 4, 9, 16, 25, 36, 49, 64, 81로, 4, 6, 8, 9와 같은 1보다 큰 소수가 아닌 수, 즉 합성수의 제곱은 그보다 낮은 소수의 제곱으로 나누어 떨어진다. 따라서 소수의 제곱으로 나누어 떨어지는지만 확인하면 그보다 큰 합성수에 대해서는 확인할 필요 없다.
2부터 Math.floor(Math.sqrt(max)) 범위 내의 모든 소수를 구한다(에라토스테네스의 체). 이후 각각의 소수마다 제곱한 값에 대해 주어진 범위 내의 배수를 구하면 된다.

코드 (JavaScript)

function main() {
    const [min, max] = require('fs').readFileSync('input.txt').toString().trim().split(' ').map(Number);
    const mid = Math.floor(Math.sqrt(max)); // 최대 100_000만 정도.

    // mid 이하의 소수 구하기. 에라토스테네스 체.
    const isPrime = new Array(mid + 1).fill(true);
    isPrime[0] = false;
    isPrime[1] = false;
    
    for (let i = 2; i <= mid; i++) {
        if (isPrime[i]) {
            let j = 2;
            while(i * j <= mid) {
                isPrime[i * j++] = false;
            }
        }
    }
    
    const answer = new Set();
    isPrime.forEach((v, i) => {
        if (v) {
            const square = Math.pow(i, 2);
            const under = Math.ceil(min / square);
            const over = Math.floor(max / square);
    
            for (let j = under; j <= over; j++) {
                answer.add(square * j);
            }
        }
    })

    console.log((max - min) + 1 - answer.size);
}

main();