Node.js) 백분 1016 제곱 ㄴㄴ 수

악.,. 알고리즘이 계속 RangeError 떠서 너무 궁금해서 테스트 해본다는게 맞았습니다..
https://lhoiktiv.tistory.com/401

Node.js)백준 1016번: 제곱 ㄴㄴ 수

이분 코드 복붙해 갔었습니다... 왜 내껀 안됐을까를 설명해보려고 합니다.

const fs = require('fs');
const [min,max] = fs.readFileSync("./dev/stdin").toString().trim().split(' ').map(Number);

// 총 개수 구하기
let count = max - min + 1;

const primeFilter = new Array(max + 1).fill(1); //RangeError 생긴 부분
// 소수 구하기
const primeNumber = [];
for (let i = 2; i <= Math.sqrt(max); i++) {
  if (primeFilter[i]) {
    primeNumber.push(i);

    for (let j = i ** 2; j <= max; j += i) {
      if (primeFilter[j]) {
        primeFilter[j] = 0;
      }
    }
  }
}
// nono가 아닌 애들 구하기
let notNoNo = new Set();
for (let i = 0; i < primeNumber.length; i++) {
  const primeDouble = primeNumber[i] * primeNumber[i];
  const startPoint = Math.ceil(min / primeDouble);

  for (let j = startPoint; j <= max / primeDouble; j++) {
    notNoNo.add(j * primeDouble);
  }
}

console.log(count - notNoNo.size);

RangeError는 허용되지 않는 범위의 값을 주려고 할 때 , 생긴다고 하더군요.

https://runebook.dev/ko/docs/javascript/global_objects/rangeerror

 

차이점은 max의 제곱근까지만 소수를 구하면 되는데 저는 max까지 에란토스체로 거르고 있었더군요...

이를 보완해도 시간초과가 떴다..

let count = max - min + 1;

const maxSqrt = Math.floor(Math.sqrt(max));
const primeFilter = new Array(maxSqrt + 1).fill(true);

const primeNumber = [];
for (let i = 2; i <= primeFilter.length; i++) {
  if (primeFilter[i]) {
    primeNumber.push(i);

    for (let j = i ** 2; j <= max; j += i) {
      if (primeFilter[j]) {
        primeFilter[j] = false;
      }
    }
  }
}

let notNoNo = new Set();
for (let i = 0; i < primeNumber.length; i++) {
  const primeDouble = primeNumber[i] * primeNumber[i];
  const startPoint = Math.ceil(min / primeDouble);

  for (let j = startPoint; j <= max / primeDouble; j++) {
    notNoNo.add(j * primeDouble);
  }
}

console.log(count - notNoNo.size);

 

이떄 에란토스체에서 최종적으로  primeNumber만 구하면 되니깐 함수로 만들어서 효율적으로 하겠다.

function sieveOfEratosthenes(max) {
  const isPrime = new Array(max + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let p = 2; p * p <= max; p++) {
    if (isPrime[p]) {
      for (let i = p * p; i <= max; i += p) {
        isPrime[i] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= max; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }

  return primes;
}

let count = max - min + 1;

const maxSqrt = Math.floor(Math.sqrt(max));
const primeNumber = sieveOfEratosthenes(maxSqrt);

let notNoNo = new Set();

for (let i = 0; i < primeNumber.length; i++) {
  const primeDouble = primeNumber[i] * primeNumber[i];
  const startPoint = Math.ceil(min / primeDouble);

  for (let j = startPoint; j <= max / primeDouble; j++) {
    notNoNo.add(j * primeDouble);
  }
}

console.log(count - notNoNo.size);

통과는 했지만 원글보다 더 느리다.. 혹시 set대신 반복문을 하는게 메모리적으로 더 효율적이지 않을까?

 

function sieveOfEratosthenes(max) {
  const isPrime = new Array(max + 1).fill(true);
  isPrime[0] = isPrime[1] = false;

  for (let p = 2; p * p <= max; p++) {
    if (isPrime[p]) {
      for (let i = p * p; i <= max; i += p) {
        isPrime[i] = false;
      }
    }
  }

  const primes = [];
  for (let i = 2; i <= max; i++) {
    if (isPrime[i]) {
      primes.push(i);
    }
  }

  return primes;
}

let count = max - min + 1;

const maxSqrt = Math.floor(Math.sqrt(max));
const primeNumber = sieveOfEratosthenes(maxSqrt);

const notNoNo = new Array(count).fill(0);

for (let i = 0; i < primeNumber.length; i++) {
  const primeDouble = primeNumber[i] * primeNumber[i];
  let startPoint = Math.ceil(min / primeDouble) * primeDouble;

  while (startPoint <= max) {
    notNoNo[startPoint - min] = 1;
    startPoint += primeDouble;
  }
}

const notNoNoCount = notNoNo.reduce((acc, val) => acc + val, 0);
console.log(count - notNoNoCount);

결국 메모리는 더 컸지만 빠른 코드가 되었다..

 

후 ...

 

후기)

 

프로그래머스에 비해서 백준이 불친절한 느낌인데, 오히려 더 깊게 생각하게 만들어서 코드 개선이 많이 되는 느낌이다.. 문제 난이도 자체는 골드랑 프로그래머스 lv1~2랑 비슷한 느낌?

수정 ) 난이도가 카카오 기출이런건 lv1이랑 프로그래머스 실버~골드 사인거 같은데, 몇몇 거품 문제가 많아서 전체적으로 골드랑 lv3이랑 비슷한 거 같습니다.