[문제]

Ryomen Sukuna has entered your body, and he will only leave if you can solve this problem.

Given an integer n, how many integers between 1 and n (inclusive) are unrepresentable as a^b, where a and b are integers not less than 2?

Example:
if n equals 10 then output must be 7,
as 4 is representable as 22, 8 as 23 and 9 as 32.
So the numbers left are 1, 2, 3, 5, 6, 7 and 10.

Note:
Optimize your solution for n as large as 1010.

(요약) 2보다 크고 주어진 숫자보다 작은 수들 중에 어떤 숫자의 n제곱으로 표현할 수 있는 수들을 제외한 숫자의 개수를 구하라. (어떤 숫자의 1제곱은 제외)

[풀이]

function sukuna(n) {
  let set = new Set();
  const max = Math.sqrt(n)|0;

  for(let i = max; i >= 2; i--) {
    squared(i, i);
  }

  function squared(num, s) {
    if(n >= num * s) {
      set.add(num * s);
      squared(num, s * num);
    }
    else{
      return;
    }
  }

  return n - set.size;
}

a의 n제곱이 주어진 숫자보다 작은 수들 중에 있을 때, a의 가장 큰 수는 주어진 숫자에 루트 2 한 수보다 작으면서 가장 큰 정수이거나 루트 2와 같은 수이다.

그래서 그 숫자보다 작은 수들을 범위로해서 반복문을 돌리면 된다.

반복문을 돌면서 재귀를 이용해 a의 n제곱이 주어진 숫자보다 작을 때까지 숫자를 set에 저장.

마지막에 n에서 set의 개수를 빼면 됨.