[백준] 1016

제곱ㄴㄴ수

문제

어떤 정수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 그 수를 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수가 몇 개 있는지 출력한다.

입력

첫째 줄에 두 정수 min과 max가 주어진다.

출력

첫째 줄에 min보다 크거나 같고, max보다 작거나 같은 제곱ㄴㄴ수의 개수를 출력한다.

제한

• 1 ≤ min ≤ 1,000,000,000,000
• min ≤ max ≤ min + 1,000,000

풀이

const noSquare = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  const range = input[1] - input[0] + 1;
  const maxSqrt = Math.floor(Math.sqrt(input[1]));
  let notSquare = Array.from({ length: range }, (n) => 1);
  let sum = 0;
  for (let i = 2; i <= maxSqrt; i++) {
    let n = i * i;
    let idx = Math.ceil(input[0] / n) * n - input[0];
    while (idx + input[0] <= input[1]) {
      notSquare[idx] = 0;
      idx += n;
    }
  }
  for (let i = 0; i < range; i++) sum += notSquare[i];
  console.log(sum);
};

noSquare();

반성회

1. 범위는 무조건 100만 이하이므로 배열은 max (input[1]) 만큼이 아닌 max - min + 1 만큼으로 선언
2. 제곱수는 MAX보다 작은 수만 검토하면 됨 ⇒ i는 sqrt(MAX) 보다 작거나 같아야 함
3. i * i = n의 배수 중 min과 가장 가깝고 min보다 약간 큰 값 idx를 찾고, idx에 n을 곱해가면서 모든 n의 배수를 0으로 만들어 지워버린다
4. 남은 1들을 더해서 개수를 센다