Given two integers L and R, the task is to count the number of pairs from the range [L, R] whose sum is a prime number in the range [L, R].
Examples:
Input: L = 1, R = 5
Output: 4
Explanation: Pairs whose sum is a prime number and in the range [L, R] are { (1, 1), (1, 2), (1, 4), (2, 3) }. Therefore, the required output is 4.Input: L = 1, R = 100
Output: 518
Naive Approach: The simplest approach to solve this problem is to generate all possible pairs from the range [1, R] and for each pair, check if the sum of elements of the pair is a prime number in the range [L, R] or not. If found to be true, then increment count. Finally, print the value of count.
Time Complexity: O(N5 / 2)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach the idea is based on the following observations:
If N is a prime number, then pairs whose sum is N are { (1, N – 1), (2, N – 2), ….., floor(N / 2), ceil(N / 2) }. Therefore, total count of pairs whose sum is N = N / 2
Follow the steps below to solve the problem:
- Initialize a variable say, cntPairs to store the count of pairs such that the sum of elements of the pair is a prime number and in the range [L, R].
- Initialize an array say segmentedSieve[] to store all the prime numbers in the range [L, R] using Sieve of Eratosthenes.
- Traverse the segment
tedSieve[] using the variable i and check if i is a prime number or not. If found to be true then increment the value of cntPairs by (i / 2). - Finally, print the value of cntPairs.
Below is the implementation of the above approach:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Function to find all prime numbers in range// [1, lmt] using sieve of Eratosthenesvoid simpleSieve(int lmt, vector<int>& prime){ // segmentedSieve[i]: Stores if i is // a prime number (True) or not (False) bool Sieve[lmt + 1]; // Initialize all elements of // segmentedSieve[] to false memset(Sieve, true, sizeof(Sieve)); // Set 0 and 1 as non-prime Sieve[0] = Sieve[1] = false; // Iterate over the range [2, lmt] for (int i = 2; i <= lmt; ++i) { // If i is a prime number if (Sieve[i] == true) { // Append i into prime prime.push_back(i); // Set all multiple of i non-prime for (int j = i * i; j <= lmt; j += i) { // Update Sieve[j] Sieve[j] = false; } } }}// Function to find all the prime numbers// in the range [low, high]vector<bool> SegmentedSieveFn( int low, int high){ // Stores square root of high + 1 int lmt = floor(sqrt(high)) + 1; // Stores all the prime numbers // in the range [1, lmt] vector<int> prime; // Find all the prime numbers in // the range [1, lmt] simpleSieve(lmt, prime); // Stores count of elements in // the range [low, high] int n = high - low + 1; // segmentedSieve[i]: Check if (i - low) // is a prime number or not vector<bool> segmentedSieve(n + 1, true); // Traverse the array prime[] for (int i = 0; i < prime.size(); i++) { // Store smallest multiple of prime[i] // in the range[low, high] int lowLim = floor(low / prime[i]) * prime[i]; // If lowLim is less than low if (lowLim < low) { // Update lowLim lowLim += prime[i]; } // Iterate over all multiples of prime[i] for (int j = lowLim; j <= high; j += prime[i]) { // If j not equal to prime[i] if (j != prime[i]) { // Update segmentedSieve[j - low] segmentedSieve[j - low] = false; } } } return segmentedSieve;}// Function to count the number of pairs// in the range [L, R] whose sum is a// prime number in the range [L, R]int countPairsWhoseSumPrimeL_R(int L, int R){ // segmentedSieve[i]: Check if (i - L) // is a prime number or not vector<bool> segmentedSieve = SegmentedSieveFn(L, R); // Stores count of pairs whose sum of // elements is a prime and in range [L, R] int cntPairs = 0; // Iterate over [L, R] for (int i = L; i <= R; i++) { // If (i - L) is a prime if (segmentedSieve[i - L]) { // Update cntPairs cntPairs += i / 2; } } return cntPairs;}// Driver Codeint main(){ int L = 1, R = 5; cout << countPairsWhoseSumPrimeL_R(L, R); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG{// Function to find all prime numbers in range// [1, lmt] using sieve of Eratosthenesstatic ArrayList<Integer> simpleSieve(int lmt, ArrayList<Integer> prime){ // segmentedSieve[i]: Stores if i is // a prime number (True) or not (False) boolean[] Sieve = new boolean[lmt + 1]; // Initialize all elements of // segmentedSieve[] to false Arrays.fill(Sieve, true); // Set 0 and 1 as non-prime Sieve[0] = Sieve[1] = false; // Iterate over the range [2, lmt] for(int i = 2; i <= lmt; ++i) { // If i is a prime number if (Sieve[i] == true) { // Append i into prime prime.add(i); // Set all multiple of i non-prime for(int j = i * i; j <= lmt; j += i) { // Update Sieve[j] Sieve[j] = false; } } } return prime;}// Function to find all the prime numbers// in the range [low, high]static boolean[] SegmentedSieveFn(int low, int high){ // Stores square root of high + 1 int lmt = (int)(Math.sqrt(high)) + 1; // Stores all the prime numbers // in the range [1, lmt] ArrayList<Integer> prime = new ArrayList<Integer>(); // Find all the prime numbers in // the range [1, lmt] prime = simpleSieve(lmt, prime); // Stores count of elements in // the range [low, high] int n = high - low + 1; // segmentedSieve[i]: Check if (i - low) // is a prime number or not boolean[] segmentedSieve = new boolean[n + 1]; Arrays.fill(segmentedSieve, true); // Traverse the array prime[] for(int i = 0; i < prime.size(); i++) { // Store smallest multiple of prime[i] // in the range[low, high] int lowLim = (int)(low / prime.get(i)) * prime.get(i); // If lowLim is less than low if (lowLim < low) { // Update lowLim lowLim += prime.get(i); } // Iterate over all multiples of prime[i] for(int j = lowLim; j <= high; j += prime.get(i)) { // If j not equal to prime[i] if (j != prime.get(i)) { // Update segmentedSieve[j - low] segmentedSieve[j - low] = false; } } } return segmentedSieve;}// Function to count the number of pairs// in the range [L, R] whose sum is a// prime number in the range [L, R]static int countPairsWhoseSumPrimeL_R(int L, int R){ // segmentedSieve[i]: Check if (i - L) // is a prime number or not boolean[] segmentedSieve = SegmentedSieveFn(L, R); // Stores count of pairs whose sum of // elements is a prime and in range [L, R] int cntPairs = 0; // Iterate over [L, R] for(int i = L; i <= R; i++) { // If (i - L) is a prime if (segmentedSieve[i - L]) { // Update cntPairs cntPairs += i / 2; } } return cntPairs;}// Driver Codepublic static void main(String[] args){ int L = 1, R = 5; System.out.println( countPairsWhoseSumPrimeL_R(L, R));}}// This code is contributed by akhilsaini |
Python
# Python program to implement# the above approachimport math# Function to find all prime numbers in range# [1, lmt] using sieve of Eratosthenesdef simpleSieve(lmt, prime): # segmentedSieve[i]: Stores if i is # a prime number (True) or not (False) Sieve = [True] * (lmt + 1) # Set 0 and 1 as non-prime Sieve[0] = Sieve[1] = False # Iterate over the range [2, lmt] for i in range(2, lmt + 1): # If i is a prime number if (Sieve[i] == True): # Append i into prime prime.append(i) # Set all multiple of i non-prime for j in range(i * i, int(math.sqrt(lmt)) + 1, i): # Update Sieve[j] Sieve[j] = false return prime# Function to find all the prime numbers# in the range [low, high]def SegmentedSieveFn(low, high): # Stores square root of high + 1 lmt = int(math.sqrt(high)) + 1 # Stores all the prime numbers # in the range [1, lmt] prime = [] # Find all the prime numbers in # the range [1, lmt] prime = simpleSieve(lmt, prime) # Stores count of elements in # the range [low, high] n = high - low + 1 # segmentedSieve[i]: Check if (i - low) # is a prime number or not segmentedSieve = [True] * (n + 1) # Traverse the array prime[] for i in range(0, len(prime)): # Store smallest multiple of prime[i] # in the range[low, high] lowLim = int(low // prime[i]) * prime[i] # If lowLim is less than low if (lowLim < low): # Update lowLim lowLim += prime[i] # Iterate over all multiples of prime[i] for j in range(lowLim, high + 1, prime[i]): # If j not equal to prime[i] if (j != prime[i]): # Update segmentedSieve[j - low] segmentedSieve[j - low] = False return segmentedSieve# Function to count the number of pairs# in the range [L, R] whose sum is a# prime number in the range [L, R]def countPairsWhoseSumPrimeL_R(L, R): # segmentedSieve[i]: Check if (i - L) # is a prime number or not segmentedSieve = SegmentedSieveFn(L, R) # Stores count of pairs whose sum of # elements is a prime and in range [L, R] cntPairs = 0 # Iterate over [L, R] for i in range(L, R + 1): # If (i - L) is a prime if (segmentedSieve[i - L] == True): # Update cntPairs cntPairs += i / 2 return cntPairs# Driver Codeif __name__ == '__main__': L = 1 R = 5 print(countPairsWhoseSumPrimeL_R(L, R))# This code is contributed by akhilsaini |
C#
// C# program to implement// the above approachusing System;using System.Collections;class GFG{// Function to find all prime numbers in range// [1, lmt] using sieve of Eratosthenesstatic ArrayList simpleSieve(int lmt, ArrayList prime){ // segmentedSieve[i]: Stores if i is // a prime number (True) or not (False) bool[] Sieve = new bool[lmt + 1]; // Initialize all elements of // segmentedSieve[] to false Array.Fill(Sieve, true); // Set 0 and 1 as non-prime Sieve[0] = Sieve[1] = false; // Iterate over the range [2, lmt] for(int i = 2; i <= lmt; ++i) { // If i is a prime number if (Sieve[i] == true) { // Append i into prime prime.Add(i); // Set all multiple of i non-prime for(int j = i * i; j <= lmt; j += i) { // Update Sieve[j] Sieve[j] = false; } } } return prime;}// Function to find all the prime numbers// in the range [low, high]static bool[] SegmentedSieveFn(int low, int high){ // Stores square root of high + 1 int lmt = (int)(Math.Sqrt(high)) + 1; // Stores all the prime numbers // in the range [1, lmt] ArrayList prime = new ArrayList(); // Find all the prime numbers in // the range [1, lmt] prime = simpleSieve(lmt, prime); // Stores count of elements in // the range [low, high] int n = high - low + 1; // segmentedSieve[i]: Check if (i - low) // is a prime number or not bool[] segmentedSieve = new bool[n + 1]; Array.Fill(segmentedSieve, true); // Traverse the array prime[] for(int i = 0; i < prime.Count; i++) { // Store smallest multiple of prime[i] // in the range[low, high] int lowLim = (int)(low / (int)prime[i]) * (int)prime[i]; // If lowLim is less than low if (lowLim < low) { // Update lowLim lowLim += (int)prime[i]; } // Iterate over all multiples of prime[i] for(int j = lowLim; j <= high; j += (int)prime[i]) { // If j not equal to prime[i] if (j != (int)prime[i]) { // Update segmentedSieve[j - low] segmentedSieve[j - low] = false; } } } return segmentedSieve;}// Function to count the number of pairs// in the range [L, R] whose sum is a// prime number in the range [L, R]static int countPairsWhoseSumPrimeL_R(int L, int R){ // segmentedSieve[i]: Check if (i - L) // is a prime number or not bool[] segmentedSieve = SegmentedSieveFn(L, R); // Stores count of pairs whose sum of // elements is a prime and in range [L, R] int cntPairs = 0; // Iterate over [L, R] for(int i = L; i <= R; i++) { // If (i - L) is a prime if (segmentedSieve[i - L]) { // Update cntPairs cntPairs += i / 2; } } return cntPairs;}// Driver Codepublic static void Main(){ int L = 1, R = 5; Console.Write(countPairsWhoseSumPrimeL_R(L, R));}}// This code is contributed by akhilsaini |
Javascript
<script>// Javascript program to implement// the above approach// Function to find all prime numbers in range// [1, lmt] using sieve of Eratosthenesfunction simpleSieve(lmt, prime){ // segmentedSieve[i]: Stores if i is // a prime number (True) or not (False) let Sieve = new Array(lmt + 1); // Initialize all elements of // segmentedSieve[] to false Sieve.fill(true) // Set 0 and 1 as non-prime Sieve[0] = Sieve[1] = false; // Iterate over the range [2, lmt] for (let i = 2; i <= lmt; ++i) { // If i is a prime number if (Sieve[i] == true) { // Append i into prime prime.push(i); // Set all multiple of i non-prime for (let j = i * i; j <= lmt; j += i) { // Update Sieve[j] Sieve[j] = false; } } }}// Function to find all the prime numbers// in the range [low, high]function SegmentedSieveFn(low, high){ // Stores square root of high + 1 let lmt = Math.floor(Math.sqrt(high)) + 1; // Stores all the prime numbers // in the range [1, lmt] let prime = new Array(); // Find all the prime numbers in // the range [1, lmt] simpleSieve(lmt, prime); // Stores count of elements in // the range [low, high] let n = high - low + 1; // segmentedSieve[i]: Check if (i - low) // is a prime number or not let segmentedSieve = new Array(n + 1).fill(true); // Traverse the array prime[] for (let i = 0; i < prime.length; i++) { // Store smallest multiple of prime[i] // in the range[low, high] let lowLim = Math.floor(low / prime[i]) * prime[i]; // If lowLim is less than low if (lowLim < low) { // Update lowLim lowLim += prime[i]; } // Iterate over all multiples of prime[i] for (let j = lowLim; j <= high; j += prime[i]) { // If j not equal to prime[i] if (j != prime[i]) { // Update segmentedSieve[j - low] segmentedSieve[j - low] = false; } } } return segmentedSieve;}// Function to count the number of pairs// in the range [L, R] whose sum is a// prime number in the range [L, R]function countPairsWhoseSumPrimeL_R(L, R){ // segmentedSieve[i]: Check if (i - L) // is a prime number or not let segmentedSieve = SegmentedSieveFn(L, R); // Stores count of pairs whose sum of // elements is a prime and in range [L, R] let cntPairs = 0; // Iterate over [L, R] for (let i = L; i <= R; i++) { // If (i - L) is a prime if (segmentedSieve[i - L]) { // Update cntPairs cntPairs += Math.floor(i / 2); } } return cntPairs;}// Driver Code let L = 1, R = 5; document.write(countPairsWhoseSumPrimeL_R(L, R)); // This code is contributed by gfgking </script> |
Output:
4
Time Complexity: O((R ? L + 1) * log?(log?(R)) + sqrt(R) * log?(log?(sqrt(R)))
Auxiliary Space: O(R – L + 1 + sqrt(R))
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!
