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. |
Output
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> |
Output
(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)
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!
