Q2. There is a range given n and m in which we have to find the count of all the prime pairs whose difference is 6. We have to find how many sets are there within a given range. Output:
Answers
Answer:
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).
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
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.
Time Complexity: O(sqrt((N))*(R – L + 1)2), 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:
Output
(5, 11) (7, 13) (11, 17) (13, 19)
Time Complexity: O(N*log*(log(N)) + sqrt(R – L)), where N = R – L + 1
Auxiliary Space: O(N)
Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course
Explanation:
There is a range given n and m in which we have to find the count all the prime pairs whose difference is 6.