[LeetCode] Count Primes

문제 

Given an integer n, return the number of prime numbers that are strictly less than n.

주어진 숫자 n을 가지고 n보다 작은 숫자들 중 소수를 찾아 리턴하시오

풀이 

에라토스테네스의 체 를 활용해 문제를 풀어야겠다고 생각하여. n보다 작은 숫자로 배열을 만들고, 2,3,5,7의 배수가 아닌 수를 순차적으로 filter해주는 방법을 생각하여 문제를 풀었다.

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // prime numbers : 2, 3, 5, 7
    
    if (n <= 2) return 0;
    
    let array = Array.from({length:n-1},(v,i) => i + 1);
    
    
    array = array.filter((el) => el % 2 != 0 || el == 2);
    
    array = array.filter((el) => el != 1)
    if (n > 3) array = array.filter((el) => el % 3 != 0 || el == 3);
    if (n > 5) array = array.filter((el) => el % 5 != 0 || el == 5);
    if (n > 7) array = array.filter((el) => el % 7 != 0 || el == 7);

    return array.length;
    
};

수정 

ChatGpt가 제안하는 답은 아래와 같다.

var countPrimes = function(n) {
    if (n <= 2) return 0;

    // Initialize an array to mark non-prime numbers
    const isPrime = new Array(n).fill(true);
    isPrime[0] = isPrime[1] = false; // 0 and 1 are not prime

    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {
            // Mark multiples of prime numbers as non-prime
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // Count the prime numbers
    return isPrime.filter((value) => value === true).length;
};

소수의 배수에 해당하는 숫자를 차례로 false처리를 해준다.

/**
 * @param {number} n
 * @return {number}
 */
const countPrimes = (n) => {
  let count = 0;
  let array = [];
  for (let i = 2; i < n; i++) {
    if (array[i]) continue
    else count++
    for (let j = i+i; j <= n; j+=i) array[j] = true
  }
  
  return count
};