Closest Prime Numbers in Range

MediumMathNumber Theory

문제 설명

  1. 두 정수 left와 right가 주어집니다.
    • left ≤ num1 < num2 ≤ right
  2. num1과 num2 모두 소수여야 합니다.
  3. num1 - num2 값이 가장 작은 쌍을 찾아 반환합니다.
    • 조건을 만족하는 쌍이 여러 개라면, 더 작은 num1을 가진 쌍을 반환합니다.
    • 조건을 만족하는 쌍이 없다면, [-1, -1]을 반환합니다.

문제 풀이

Sieve of Eratosthenes(에라토스테네스의 체)

  1. 소수 판별
  2. left 부터 right 까지의 범위 내에서 가장 가까운 소수 쌍 찾기
    • prevPrime 변수를 사용해 이전 소수와 현재 소수간의 차이를 계산
    • num1 - num2 가 가장 작은 값을 가진 소수 쌍을 찾아서 반환
function closestPrimes(left: number, right: number): number[] {
  const isPrime = sieve(right);
 
  let answer = [-1, -1];
  let prevPrime = -1;
  let minDiff = Number.MAX_SAFE_INTEGER;
  for (let num = left; num <= right; num++) {
    if (!isPrime[num]) continue;
    if (prevPrime !== -1 && num - prevPrime < minDiff) {
      minDiff = num - prevPrime;
      answer = [prevPrime, num];
    }
    prevPrime = num;
  }
  return answer;
}
 
function sieve(limit: number): boolean[] {
  const isPrime = new Array<boolean>(limit + 1).fill(true);
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i * i <= limit; i++) {
    if (!isPrime[i]) continue;
    for (let j = i * i; j <= limit; j += i) {
      isPrime[j] = false;
    }
  }
  return isPrime;
}

복잡도

  • 시간 복잡도: O(R⋅log(log(R))+R−L)O(R \cdot log(log(R)) + R - L)
  • 공간 복잡도: O(R)O(R)
LeetCode
Closest Prime Numbers in Range
https://leetcode.com/problems/closest-prime-numbers-in-range/