Minimum difference between any two primes from the given range

0 0 7 minutes read

Given two integers L and R, the task is to find the minimum difference between any two prime numbers in the range [L, R].

Examples:

Input: L = 21, R = 50
Output: 2
(29, 31) and (41, 43) are the only valid pairs
that give the minimum difference.

Input: L = 1, R = 11
Output: 1
The difference between (2, 3) is minimum.

Approach:

Find all the prime numbers upto R using Sieve of Eratosthenes.
Now starting from L, find the difference between any two prime numbers within the range and update minimum difference so far.
If the number of primes in the range were < 2 then print -1.
Else print the minimum difference.

Below is the implementation of the above approach:

C++14

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5;
bool isPrime[sz + 1];
 
// Function for Sieve of Eratosthenes
void sieve()
{
    memset(isPrime, true, sizeof(isPrime));
 
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i * i <= sz; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < sz; j += i) {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
int minDifference(int L, int R)
{
 
    // Find the first prime from the range
    int fst = 0;
    for (int i = L; i <= R; i++) {
 
        if (isPrime[i]) {
            fst = i;
            break;
        }
    }
 
    // Find the second prime from the range
    int snd = 0;
    for (int i = fst + 1; i <= R; i++) {
 
        if (isPrime[i]) {
            snd = i;
            break;
        }
    }
 
    // If the number of primes in
    // the given range is < 2
    if (snd == 0)
        return -1;
 
    // To store the minimum difference between
    // two consecutive primes from the range
    int diff = snd - fst;
 
    // Range left to check for primes
    int left = snd + 1;
    int right = R;
 
    // For every integer in the range
    for (int i = left; i <= right; i++) {
 
        // If the current integer is prime
        if (isPrime[i]) {
 
            // If the difference between i
            // and snd is minimum so far
            if (i - snd <= diff) {
 
                fst = snd;
                snd = i;
                diff = snd - fst;
            }
        }
    }
 
    return diff;
}
 
// Driver code
int main()
{
    // Generate primes
    sieve();
 
    int L = 21, R = 50;
 
    cout << minDifference(L, R);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
     
static int sz = (int) 1e5;
static boolean []isPrime = new boolean [sz + 1];
 
// Function for Sieve of Eratosthenes
static void sieve()
{
    Arrays.fill(isPrime, true);
 
    isPrime[0] = isPrime[1] = false;
 
    for (int i = 2; i * i <= sz; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j < sz; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
static int minDifference(int L, int R)
{
 
    // Find the first prime from the range
    int fst = 0;
    for (int i = L; i <= R; i++) 
    {
        if (isPrime[i])
        {
            fst = i;
            break;
        }
    }
 
    // Find the second prime from the range
    int snd = 0;
    for (int i = fst + 1; i <= R; i++) 
    {
        if (isPrime[i])
        {
            snd = i;
            break;
        }
    }
 
    // If the number of primes in
    // the given range is < 2
    if (snd == 0)
        return -1;
 
    // To store the minimum difference between
    // two consecutive primes from the range
    int diff = snd - fst;
 
    // Range left to check for primes
    int left = snd + 1;
    int right = R;
 
    // For every integer in the range
    for (int i = left; i <= right; i++)
    {
 
        // If the current integer is prime
        if (isPrime[i]) 
        {
 
            // If the difference between i
            // and snd is minimum so far
            if (i - snd <= diff) 
            {
                fst = snd;
                snd = i;
                diff = snd - fst;
            }
        }
    }
    return diff;
}
 
// Driver code
public static void main(String []args) 
{
     
    // Generate primes
    sieve();
 
    int L = 21, R = 50;
    System.out.println(minDifference(L, R));
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach 
from math import sqrt
 
sz = int(1e5); 
isPrime = [True] * (sz + 1); 
 
# Function for Sieve of Eratosthenes 
def sieve() :
 
    isPrime[0] = isPrime[1] = False; 
 
    for i in range(2, int(sqrt(sz)) + 1) :
        if (isPrime[i]) :
            for j in range(i * i, sz, i) :
                isPrime[j] = False; 
     
# Function to return the minimum difference 
# between any two prime numbers 
# from the given range [L, R] 
def minDifference(L, R) : 
 
    # Find the first prime from the range 
    fst = 0; 
    for i in range(L, R + 1) :
 
        if (isPrime[i]) :
            fst = i; 
            break; 
 
    # Find the second prime from the range 
    snd = 0; 
    for i in range(fst + 1, R + 1) :
 
        if (isPrime[i]) :
            snd = i; 
            break; 
             
    # If the number of primes in 
    # the given range is < 2 
    if (snd == 0) :
        return -1; 
 
    # To store the minimum difference between 
    # two consecutive primes from the range 
    diff = snd - fst; 
 
    # Range left to check for primes 
    left = snd + 1; 
    right = R; 
 
    # For every integer in the range 
    for i in range(left, right + 1) :
 
        # If the current integer is prime 
        if (isPrime[i]) :
 
            # If the difference between i 
            # and snd is minimum so far 
            if (i - snd <= diff) :
 
                fst = snd; 
                snd = i; 
                diff = snd - fst; 
 
    return diff; 
 
# Driver code 
if __name__ == "__main__" : 
 
    # Generate primes 
    sieve(); 
 
    L = 21; R = 50; 
 
    print(minDifference(L, R)); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
                     
class GFG 
{
     
static int sz = (int) 1e5;
static Boolean []isPrime = new Boolean [sz + 1];
 
// Function for Sieve of Eratosthenes
static void sieve()
{
    for(int i = 2; i< sz + 1; i++)
        isPrime[i] = true;
 
    for (int i = 2; i * i <= sz; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j < sz; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
static int minDifference(int L, int R)
{
 
    // Find the first prime from the range
    int fst = 0;
    for (int i = L; i <= R; i++) 
    {
        if (isPrime[i])
        {
            fst = i;
            break;
        }
    }
 
    // Find the second prime from the range
    int snd = 0;
    for (int i = fst + 1; i <= R; i++) 
    {
        if (isPrime[i])
        {
            snd = i;
            break;
        }
    }
 
    // If the number of primes in
    // the given range is < 2
    if (snd == 0)
        return -1;
 
    // To store the minimum difference between
    // two consecutive primes from the range
    int diff = snd - fst;
 
    // Range left to check for primes
    int left = snd + 1;
    int right = R;
 
    // For every integer in the range
    for (int i = left; i <= right; i++)
    {
 
        // If the current integer is prime
        if (isPrime[i]) 
        {
 
            // If the difference between i
            // and snd is minimum so far
            if (i - snd <= diff) 
            {
                fst = snd;
                snd = i;
                diff = snd - fst;
            }
        }
    }
    return diff;
}
 
// Driver code
public static void Main(String []args) 
{
     
    // Generate primes
    sieve();
 
    int L = 21, R = 50;
    Console.WriteLine(minDifference(L, R));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation of the approach
const sz = 1e5;
let isPrime = new Array(sz + 1);
 
// Function for Sieve of Eratosthenes
function sieve() 
{
    isPrime.fill(true);
    isPrime[0] = isPrime[1] = false;
 
    for(let i = 2; i * i <= sz; i++) 
    {
        if (isPrime[i]) 
        {
            for(let j = i * i; j < sz; j += i)
            {
                isPrime[j] = false;
            }
        }
    }
}
 
// Function to return the minimum difference
// between any two prime numbers
// from the given range [L, R]
function minDifference(L, R)
{
     
    // Find the first prime from the range
    let fst = 0;
    for(let i = L; i <= R; i++) 
    {
        if (isPrime[i]) 
        {
            fst = i;
            break;
        }
    }
 
    // Find the second prime from the range
    let snd = 0;
    for(let i = fst + 1; i <= R; i++)
    {
        if (isPrime[i])
        {
            snd = i;
            break;
        }
    }
 
    // If the number of primes in
    // the given range is < 2
    if (snd == 0)
        return -1;
 
    // To store the minimum difference between
    // two consecutive primes from the range
    let diff = snd - fst;
 
    // Range left to check for primes
    let left = snd + 1;
    let right = R;
 
    // For every integer in the range
    for(let i = left; i <= right; i++)
    {
         
        // If the current integer is prime
        if (isPrime[i])
        {
             
            // If the difference between i
            // and snd is minimum so far
            if (i - snd <= diff) 
            {
                fst = snd;
                snd = i;
                diff = snd - fst;
            }
        }
    }
    return diff;
}
 
// Driver code
 
// Generate primes
sieve();
 
let L = 21, R = 50;
 
document.write(minDifference(L, R));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output:

Time Complexity: O((R – L) + sqrt(10⁵))

Auxiliary Space: O(10⁵)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!