LeetCode Entry

2523. Closest Prime Numbers in Range

07.03.2025 medium 2025 kotlin rust

Min diff primes pair in left..right

2523. Closest Prime Numbers in Range medium blog post substack youtube 1.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/918

Problem TLDR

Min diff primes pair in left..right #medium #math

Intuition

I didn’t remember the Sieve of Eratosthenes algorithm, but brute-force with sqrt(max) optimization was accepted. The sieve works like this:

  • iterate 2..n
  • skip marked as non-primes
  • mark current prime with all multipliers 2..n as non-prime
  • https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

Approach

  • the naive approach has O(1) memory

Complexity

  • Time complexity: \(O(nlog(log(n)))\), or O(nsqrt(n))

  • Space complexity: \(O(n)\) or O(1)

Code


    fun closestPrimes(l: Int, r: Int) = {
        val p = IntArray(r + 1)
        for (x in 2..r) if (p[x] < 1) for (j in 2..r / x) p[x * j] = 1
        (max(2, l)..r).filter { p[it] < 1 }.windowed(2)
            .minByOrNull { it[1] - it[0] } ?: listOf(-1, -1)
    }()



    fun closestPrimes(left: Int, right: Int): IntArray {
        var p = 0; var diff = 1000000; val r = intArrayOf(-1, -1)
        for (x in left..right) {
            var i = 2; var prime = true
            while (i * i <= x && prime) if (x % i++ == 0) prime = false
            if (prime && x > 1 && p > 0 && x - p < diff) { diff = x - p; r[0] = p; r[1] = x }
            if (prime && x > 1) p = x
        }
        return r
    }



    pub fn closest_primes(l: i32, r: i32) -> Vec<i32> {
        let (mut p, mut g) = (vec![0; 1 + r as usize], vec![]);
        for x in 2..=r { if p[x as usize] < 1 {
            if l <= x { g.push(x); } for j in 2..=r / x { p[(x * j) as usize] = 1 }}}
        g.windows(2).min_by_key(|w| w[1] - w[0]).unwrap_or(&[-1, -1]).to_vec()
    }



    vector<int> closestPrimes(int l, int r) {
        int p[1000001], prev = -1, d = 1e6, a = -1, b = -1;
        for (int x = 2; x <= r; x++) if (!p[x]) {
            for (int j = 2; j * x <= r; j++) p[j * x] = 1;
            if (x < l) continue;
            if (prev != -1 && x - prev < d) d = x - prev, a = prev, b = x;
            prev = x;
        }
        return {a, b};
    }