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 Eratosthenesvoid 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 codeint main(){ // Generate primes sieve(); int L = 21, R = 50; cout << minDifference(L, R); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG { static int sz = (int) 1e5;static boolean []isPrime = new boolean [sz + 1];// Function for Sieve of Eratosthenesstatic 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 codepublic 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 sqrtsz = 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 approachusing System; class GFG { static int sz = (int) 1e5;static Boolean []isPrime = new Boolean [sz + 1];// Function for Sieve of Eratosthenesstatic 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 codepublic 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 approachconst sz = 1e5;let isPrime = new Array(sz + 1);// Function for Sieve of Eratosthenesfunction 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 primessieve();let L = 21, R = 50;document.write(minDifference(L, R));// This code is contributed by _saurabh_jaiswal</script> |
Output:
2
Time Complexity: O((R – L) + sqrt(105))
Auxiliary Space: O(105)
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
