[백준] 1456

거의 소수

문제

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.

두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

입력

첫째 줄에 왼쪽 범위 A와 오른쪽 범위 B가 공백 한 칸을 사이에 두고 주어진다.

출력

첫째 줄에 총 몇 개가 있는지 출력한다.

제한

• 1 ≤ A ≤ B ≤ 10^14

풀이

const almost = () => {
  let [a, b] = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split(" ")
    .map(Number);
  let eratos = Array.from({ length: 10000001 }, (n, i) =>
    i === 1 ? false : true
  );
  for (let i = 2; i < 3163; i++) {
    if (eratos[i]) for (let j = 2; j < 10000002 / i; j++) eratos[i * j] = false;
  }

  let ans = 0;
  const rootB = Math.sqrt(b);
  for (let i = 1; i <= 10000000; i++) {
    if (eratos[i]) {
      let pow = i * i;
      while (pow <= b) {
        if (pow >= a) ans++;
        pow *= i;
      }
    }
  }

  console.log(ans);
};

almost();

반성회

a와 b의 범위가 10의 14승이기 때문에 에라토스테네스의 체도 10의 7승까지는 전부 해주어야 함

이 부분에서 상당히 오래 걸릴 줄 알았는데 시간제한 2초로 좀 넉넉해서 무난히 통과했다