프라임 카운트

문제 #

이것은 내가 n차까지 복잡하게 만든 또 다른 간단한 문제입니다. 비록 내가 거기에 도착했고 내가 요점이라고 생각하는 길을 따라 뭔가를 배웠지만. 먼저 소수란 무엇인가? 소수는 1과 자기 자신으로만 나누어 떨어지는 1보다 큰 정수입니다. 그래서 정의입니다. 이제 CPU 뱅크를 깨지 않고 주어진 소수를 계산하는 방법에 대해 알아보겠습니다. 나는 아주 오래된 에라토스테네스의 체라는 멋진 알고리즘을 발견했습니다. 기원전 200년경에 처음 등장하지만 기원전 300년만큼 오래되었을 수도 있습니다. 따라서 현대의 기계가 수학을 처리할 수 있어야 한다고 가정해 보겠습니다. 원한다면 그것에 대해 더 자세히 읽을 수 있습니다here.

내 첫 번째 시도는 무차별 대입 접근 방식이었고 소수가 아닌 경우 배열에서 제거할 배열을 사용했습니다. 이것은 더 낮은 숫자에서 작동했지만 더 높은 숫자에 도달함에 따라 허용되지 않았으며 Leetcode 확인에서 Time Limit Exceeded 결과를 얻었습니다.

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  if (n === 0 || n === 1) return 0;

  const primeArray = [];
  for (let i = 2; i <= n - 1; i++) {
    primeArray.push(i);
  }
  const sqrt = Math.sqrt(n);
  for (let i = 2; i <= sqrt; i++) {
    for (let j = 0; j <= primeArray.length; j++) {
      if (primeArray[j] % i === 0 && primeArray[j] !== i) {
        primeArray.splice(j, 1);
      }
    }
  }

  return primeArray.length;
};

드로잉 보드로 돌아가서 마지막을 기억하고 숫자가 소수가 아닌 횟수를 추가하고 숫자가 여전히 0인 개수를 반환할 수 있었습니다. 이것은 훨씬 빠르게 실행되었고 내 로컬 컴퓨터에서 빠르게 결과를 얻었지만 다시 처리 시간으로 인해 방해를 받았습니다.

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  if (n === 0 || n === 1) return 0;

  const primeMap = {};
  // for (let i = 2; i <= n - 1; i++) {
  // primeArray.push(i);
  // }
  //console.log(primeArray);
  const sqrt = Math.sqrt(n);
  for (let i = 2; i <= sqrt; i++) {
    for (let j = 2; j < n; j++) {
      if (primeMap[j] === undefined) {
        primeMap[j] = 0;
      }
      if (j % i === 0 && i!==j) {
        primeMap[j]++;
      }
    }
  }
  let result = 0;
  for(let i = 0; i<= n;i++){
    if(primeMap[i]===0) result++;
  }

  return result;
};

궁극적인 해결책이 저에게 떠올랐습니다. 내가 왜 그렇게 복잡하게 했는지. 숫자가 소수인지 확인하는 도우미 함수가 있다면 숫자 목록을 반복하고 소수인지 아닌지 카운터에 추가할 수 있습니다. 그리고 그것은 받아들여졌습니다.

const isPrime = (n) => {
  // Check if number is less than
  // equal to 1
  if (n <= 1) return false;
  // Check if number is 2
  else if (n == 2) return true;
  // Check if n is a multiple of 2
  else if (n % 2 == 0) return false;

  // If not, then just check the odds
  for (let i = 3; i <= Math.sqrt(n); i += 2) {
    if (n % i == 0) return false;
  }
  return true;
};

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function (n) {
  let result = 0;
  for (let i = 1; i < n; i++) {
    if (isPrime(i)) {
      result++;
    }
  }
  return result;
};

내가 배운 것 #

솔루션을 단순화하십시오

도우미 기능 사용