2523.js

/** ------------------------------------------------------------------------------
 * 
 * 2523. Closest Prime Numbers in Range
 * Topics: Math
 * https://leetcode.com/problems/closest-prime-numbers-in-range/description/?envType=daily-question&envId=2025-03-07
 * 
 ------------------------------------------------------------------------------ */
/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
// var closestPrimes = function (left, right) {
//   const primeNumbers = []

//   for (let i = left <= 1 ? 2 : left; i <= right; i++) {
//     if (isPrimeNumber(i)) {
//       primeNumbers.push(i)
//     }
//   }

//   if (primeNumbers.length <= 1) {
//     return [-1, -1]
//   }

//   const answer = [0, 0]
//   let minDiff = Number.MAX_SAFE_INTEGER

//   for (let i = 1; i < primeNumbers.length; i++) {
//     const absDiff = Math.abs(primeNumbers[i] - primeNumbers[i - 1])
//     if (absDiff < minDiff) {
//       minDiff = absDiff
//       answer[0] = primeNumbers[i - 1]
//       answer[1] = primeNumbers[i]
//     }
//   }
//   return answer
// }

// const isPrimeNumber = (n) => {
//   let factors = 0
//   for (let i = 1; i <= Math.sqrt(n); i++) {
//     if (n % i === 0) {
//       factors += 1
//       if (n / i !== i) {
//         factors += 1
//       }
//     }
//     if (factors > 2) {
//       return false
//     }
//   }
//   return true
// }

/** ------------------------------------------------------------------------------
 * 
 * 시간복잡도 효율
 * 
 ------------------------------------------------------------------------------ */
const MAX = 10 ** 6

const primes = (() => {
  const res = []
  for (let i = 3; i <= MAX; i += 2) {
    let isPrime = true
    for (const p of res) {
      if (i % p === 0) {
        isPrime = false
        break
      }
      if (p * p > i) {
        break
      }
    }
    if (isPrime) {
      res.push(i)
    }
  }

  res.unshift(2)
  return res
})()

/**
 * @param {number} left
 * @param {number} right
 * @return {number[]}
 */
function closestPrimes(left, right) {
  let res = null
  for (let i = 1; i < primes.length; ++i) {
    const a = primes[i - 1]
    const b = primes[i]
    if (left <= a && b <= right && (res == null || b - a < res[1] - res[0])) {
      res = [a, b]
    }
  }
  return res ?? [-1, -1]
}

console.log(closestPrimes(10, 10))