Given two integers L, R, and an integer K, the task is to print all the pairs of Prime Numbers from the given range whose difference is K.
Examples:
Input: L = 1, R = 19, K = 6
Output: (5, 11) (7, 13) (11, 17) (13, 19)
Explanation: The pairs of prime numbers with difference 6 are (5, 11), (7, 13), (11, 17), and (13, 19).Input: L = 4, R = 13, K = 2
Output: (5, 7) (11, 13)
Explanation: The pairs of prime numbers with difference 2 are (5, 7) and (11, 13).
Naive Approach: The simplest approach is to generate all possible pairs having difference K from the given range and check if both the pair elements are Prime Numbers or not. If there exists such a pair, then print that pair.Â
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to check if given number is prime numbersbool isPrime(int N){Â Â Â Â for (int i = 2; i <= sqrt(N); i++) {Â Â Â Â Â Â Â Â if (N % i == 0)Â Â Â Â Â Â Â Â Â Â Â Â return false;Â Â Â Â }Â Â Â Â return true;}Â
// Function to print all the prime pairs// in the given range that differs by Kvoid getPrimePairs(int L, int R, int K){Â Â Â Â int count = 0;Â
    // Iterate over the given range    for (int i = L; i <= R; i++) {Â
        // Check if pair (i, i + k) both are prime or not        if (isPrime(i) && isPrime(i + K)) {            count++;        }    }Â
      // Print the total count    cout << count << endl;}Â
// Driver Codeint main(){    // Given range    int L = 4, R = 13;Â
    // Given K    int K = 2;Â
    // Function Call    getPrimePairs(L, R, K);Â
    return 0;} |
Java
import java.util.*;Â
class Main {     // Function to check if given number is prime numbers  public static boolean isPrime(int N)  {    for (int i = 2; i <= Math.sqrt(N); i++) {      if (N % i == 0)        return false;    }    return true;  }Â
  // Function to print all the prime pairs  // in the given range that differs by K  public static void getPrimePairs(int L, int R, int K)  {    int count = 0;Â
    // Iterate over the given range    for (int i = L; i <= R; i++) {Â
      // Check if pair (i, i + k) both are prime or      // not      if (isPrime(i) && isPrime(i + K)) {        count++;      }    }Â
    // Print the total count    System.out.println(count);  }Â
  // Driver Code  public static void main(String[] args)  {    // Given range    int L = 4, R = 13;Â
    // Given K    int K = 2;Â
    // Function Call    getPrimePairs(L, R, K);  }}Â
// This code is contributed by divyansh2212 |
Python3
# Python program for the above approachimport mathÂ
# Function to check if given number is prime numbersdef isPrime(N):Â Â Â Â for i in range(2, math.floor(math.sqrt(N))+1):Â Â Â Â Â Â Â Â if (N % i == 0):Â Â Â Â Â Â Â Â Â Â Â Â return False;Â Â Â Â return True;Â
# Function to print all the prime pairs# in the given range that differs by Kdef getPrimePairs(L, R, K):Â Â Â Â count = 0;Â
    # Iterate over the given range    for i in range(L, R+1):        # Check if pair (i, i + k) both are prime or not        if (isPrime(i) and isPrime(i + K)):            count+=1;               # Print the total count    print(count);Â
# Driver Code# Given rangeL = 4;R = 13;Â
# Given KK = 2;Â
# Function CallgetPrimePairs(L, R, K);Â
# This code is contributed by ritaagarwal. |
C#
// C# code for the above approachusing System;Â
class GFG {Â
  // Function to check if given number is prime numbers  public static bool IsPrime(int N)  {    for (int i = 2; i <= Math.Sqrt(N); i++) {      if (N % i == 0)        return false;    }    return true;  }Â
  // Function to print all the prime pairs  // in the given range that differs by K  public static void GetPrimePairs(int L, int R, int K)  {    int count = 0;Â
    // Iterate over the given range    for (int i = L; i <= R; i++) {Â
      // Check if pair (i, i + k) both are prime or      // not      if (IsPrime(i) && IsPrime(i + K)) {        count++;      }    }Â
    // Print the total count    Console.WriteLine(count);  }Â
  // Driver Code  public static void Main(string[] args)  {    // Given range    int L = 4, R = 13;Â
    // Given K    int K = 2;Â
    // Function Call    GetPrimePairs(L, R, K);  }}Â
// This code is contributed by lokeshpotta20. |
Javascript
// Javascript program for the above approachÂ
// Function to check if given number is prime numbersfunction isPrime(N){Â Â Â Â for (let i = 2; i <= Math.sqrt(N); i++) {Â Â Â Â Â Â Â Â if (N % i == 0)Â Â Â Â Â Â Â Â Â Â Â Â return false;Â Â Â Â }Â Â Â Â return true;}Â
// Function to print all the prime pairs// in the given range that differs by Kfunction getPrimePairs(L, R, K){Â Â Â Â let count = 0;Â
    // Iterate over the given range    for (let i = L; i <= R; i++) {Â
        // Check if pair (i, i + k) both are prime or not        if (isPrime(i) && isPrime(i + K)) {            count++;        }    }Â
      // Print the total count    console.log(count);}Â
// Driver Code// Given rangelet L = 4, R = 13;Â
// Given Klet K = 2;Â
// Function CallgetPrimePairs(L, R, K);Â
// This code is contributed by poojaagarwal2. |
2
Time Complexity: O(sqrt((N))*(R – L + 1)), where N is any number in the range [L, R].
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use the Sieve of Eratosthenes to find all the prime numbers in the given range [L, R] and store it in an unordered_map M. Now, traverse through each value(say val) in the M and if (val + K) is also present in the map M, then print the pair.
Below is the implementation of the above approach:
C++
// C++ program for the above approachÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to generate prime numbers// in the given range [L, R]void findPrimeNos(int L, int R,                  unordered_map<int,                                int>& M){    // Store all value in the range    for (int i = L; i <= R; i++) {        M[i]++;    }Â
    // Erase 1 as its non-prime    if (M.find(1) != M.end()) {        M.erase(1);    }Â
    // Perform Sieve of Eratosthenes    for (int i = 2; i <= sqrt(R); i++) {Â
        int multiple = 2;Â
        while ((i * multiple) <= R) {Â
            // Find current multiple            if (M.find(i * multiple)                != M.end()) {Â
                // Erase as it is a                // non-prime                M.erase(i * multiple);            }Â
            // Increment multiple            multiple++;        }    }}Â
// Function to print all the prime pairs// in the given range that differs by Kvoid getPrimePairs(int L, int R, int K){Â Â Â Â unordered_map<int, int> M;Â
    // Generate all prime number    findPrimeNos(L, R, M);Â
    // Traverse the Map M    for (auto& it : M) {Â
        // If it.first & (it.first + K)        // is prime then print this pair        if (M.find(it.first + K)            != M.end()) {            cout << "(" << it.first                 << ", "                 << it.first + K                 << ") ";        }    }}Â
// Driver Codeint main(){    // Given range    int L = 1, R = 19;Â
    // Given K    int K = 6;Â
    // Function Call    getPrimePairs(L, R, K);Â
    return 0;} |
Java
// Java program for the // above approachimport java.util.*;Â
class solution{Â
// Function to generate prime // numbers in the given range [L, R]static void findPrimeNos(int L, int R,                         Map<Integer,                             Integer> M,                          int K){  // Store all value in the range  for (int i = L; i <= R; i++)   {    if(M.get(i) != null)      M.put(i, M.get(i) + 1);    else      M.put(i, 1);  }Â
  // Erase 1 as its  // non-prime  if (M.get(1) != null)   {    M.remove(1);  }Â
  // Perform Sieve of   // Eratosthenes  for (int i = 2;            i <= Math.sqrt(R); i++)   {    int multiple = 2;         while ((i * multiple) <= R)     {      // Find current multiple      if (M.get(i * multiple) != null)      {        // Erase as it is a        // non-prime        M.remove(i * multiple);      }Â
      // Increment multiple      multiple++;    }  }Â
  // Traverse the Map M  for (Map.Entry<Integer,                 Integer> entry :        M.entrySet())   {    // If it.first & (it.first + K)    // is prime then print this pairÂ
    if (M.get(entry.getKey() + K) != null)     {      System.out.print("(" + entry.getKey() +                       ", " + (entry.getKey() +                        K) + ") ");    }  }}Â
// Function to print all // the prime pairs in the // given range that differs by Kstatic void getPrimePairs(int L,                           int R, int K){  Map<Integer,      Integer> M = new HashMap<Integer,                               Integer>(); Â
  // Generate all prime number  findPrimeNos(L, R, M, K);}Â
// Driver Codepublic static void main(String args[]){  // Given range  int L = 1, R = 19;Â
  // Given K  int K = 6;Â
  // Function Call  getPrimePairs(L, R, K);}}Â
// This code is contributed by SURENDRA_GANGWAR |
Python3
# Python3 program for the above approachfrom math import sqrtÂ
# Function to generate prime numbers# in the given range [L, R]def findPrimeNos(L, R, M):         # Store all value in the range    for i in range(L, R + 1):        M[i] = M.get(i, 0) + 1Â
    # Erase 1 as its non-prime    if (1 in M):        M.pop(1)Â
    # Perform Sieve of Eratosthenes    for i in range(2, int(sqrt(R)) + 1, 1):        multiple = 2Â
        while ((i * multiple) <= R):                         # Find current multiple            if ((i * multiple) in M):                                 # Erase as it is a                # non-prime                M.pop(i * multiple)Â
            # Increment multiple            multiple += 1Â
# Function to print all the prime pairs# in the given range that differs by Kdef getPrimePairs(L, R, K):Â Â Â Â Â Â Â Â Â M = {}Â
    # Generate all prime number    findPrimeNos(L, R, M)Â
    # Traverse the Map M    for key, values in M.items():                 # If it.first & (it.first + K)        # is prime then print this pair        if ((key + K) in M):            print("(", key, ",",                  key + K, ")", end = " ")Â
# Driver Codeif __name__ == '__main__':         # Given range    L = 1    R = 19Â
    # Given K    K = 6Â
    # Function Call    getPrimePairs(L, R, K)Â
# This code is contributed by bgangwar59 |
C#
// C# program for the // above approachusing System;using System.Collections.Generic;class solution{Â
// Function to generate prime // numbers in the given range [L, R]static void findPrimeNos(int L, int R,                         Dictionary<int,                          int> M, int K){  // Store all value in the range  for (int i = L; i <= R; i++)   {      if(M.ContainsKey(i))      M.Add(i, M[i] + 1);    else      M.Add(i, 1);  }Â
  // Erase 1 as its  // non-prime  if (M[1] != 0)   {    M.Remove(1);  }Â
  // Perform Sieve of   // Eratosthenes  for (int i = 2;            i <= Math.Sqrt(R); i++)   {    int multiple = 2;         while ((i * multiple) <= R)     {      // Find current multiple      if (M.ContainsKey(i * multiple))      {        // Erase as it is a        // non-prime        M.Remove(i * multiple);      }Â
      // Increment multiple      multiple++;    }  }Â
  // Traverse the Map M  foreach (KeyValuePair<int,                         int> entry in M)   {    // If it.first & (it.first + K)    // is prime then print this pairÂ
    if (M.ContainsKey(entry.Key + K))     {      Console.Write("(" + entry.Key +                    ", " + (entry.Key +                     K) + ") ");    }  }}Â
// Function to print all // the prime pairs in the // given range that differs by Kstatic void getPrimePairs(int L,                           int R, int K){  Dictionary<int,             int> M = new Dictionary<int,                                     int>();      // Generate all prime number  findPrimeNos(L, R, M, K);}Â
// Driver Codepublic static void Main(String []args){  // Given range  int L = 1, R = 19;Â
  // Given K  int K = 6;Â
  // Function Call  getPrimePairs(L, R, K);}}Â
// This code is contributed by Amit Katiyar |
Javascript
<script>Â
// Javascript program for the above approachÂ
// Function to generate prime numbers// in the given range [L, R]function findPrimeNos(L, R, M){         // Store all value in the range    for(var i = L; i <= R; i++)     {        if (M.has(i))            M.set(i, M.get(i) + 1)        else            M.set(i, 1)    }Â
    // Erase 1 as its non-prime    if (M.has(1))     {        M.delete(1);    }Â
    // Perform Sieve of Eratosthenes    for(var i = 2; i <= parseInt(Math.sqrt(R)); i++)     {        var multiple = 2;Â
        while ((i * multiple) <= R)        {                         // Find current multiple            if (M.has(i * multiple))             {                                 // Erase as it is a                // non-prime                M.delete(i * multiple);            }Â
            // Increment multiple            multiple++;        }    }    return M;}Â
// Function to print all the prime pairs// in the given range that differs by Kfunction getPrimePairs(L, R, K){    var M = new Map();Â
    // Generate all prime number    M = findPrimeNos(L, R, M);Â
    // Traverse the Map M    M.forEach((value, key) => {                 // If it.first & (it.first + K)        // is prime then print this pair        if (M.has(key + K))        {            document.write("(" + key + ", " +                           (key + K) + ") ");        }    });}Â
// Driver CodeÂ
// Given rangevar L = 1, R = 19;Â
// Given Kvar K = 6;Â
// Function CallgetPrimePairs(L, R, K);Â
// This code is contributed by rutvik_56Â
</script> |
(13, 19) (11, 17) (5, 11) (7, 13)
Time Complexity: O(N*log*(log(N)) + sqrt(R – L)), where N = R – L + 1
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

… [Trackback]
[…] Here you will find 40001 additional Information on that Topic: geeksforgeeks.org/k-distant-prime-pairs-in-a-given-range/ […]
… [Trackback]
[…] Here you can find 99804 additional Info to that Topic: geeksforgeeks.org/k-distant-prime-pairs-in-a-given-range/ […]