Find the number of ordered pairs such that a * p + b * q = N, where p and q are primes
Given an array arr[], and integer Q denoting number of queries and two numbers a, b, the task is to find the number of ordered pairs (p, q) such that a * p + b * q = arr[i], where p and q are prime numbers.
Examples:
Input: Q = 3, arr[] = { 2, 7, 11 }, a = 1, b = 2
Output: 0 1 2
Explanation:
2 -> There are no ordered pairs (p, q) such that p + 2*q = 2.
7 -> There is only one ordered pair (p, q) = (3, 2) such that p + 2*q = 7.
11 -> There are two ordered pairs (p, q) = (7, 2), (5, 3) such that p + 2*q = 11.
Input: Q = 2, arr[] = { 15, 25 }, a = 1, b = 2
Output: 2 3
Approach: The idea is to store every prime number in an array using Sieve of Eratosthenes. After storing the prime numbers, count the number of ordered pairs (p, q) such that a*p + b*q = N for every combination of (p, q) in the prime array.
Below is the implementation of the above approach:
C++
// C++ program to find the number of ordered // pairs such that a * p + b * q = N // where p and q are primes #include <bits/stdc++.h> #define size 10001 using namespace std; int prime[size]; int freq[size]; // Sieve of eratosthenes // to store the prime numbers // and their frequency in form a*p+b*q void sieve( int a, int b) { prime[1] = 1; // Performing Sieve of Eratosthenes // to find the prime numbers unto 10001 for ( int i = 2; i * i < size; i++) { if (prime[i] == 0) { for ( int j = i * 2; j < size; j += i) prime[j] = 1; } } // Loop to find the number of // ordered pairs for every combination // of the prime numbers for ( int p = 1; p < size; p++) { for ( int q = 1; q < size; q++) { if (prime[p] == 0 && prime[q] == 0 && a * p + b * q < size) { freq[a * p + b * q]++; } } } } // Driver code int main() { int queries = 2, a = 1, b = 2; sieve(a, b); int arr[queries] = { 15, 25 }; // Printing the number of ordered pairs // for every query for ( int i = 0; i < queries; i++) { cout << freq[arr[i]] << " " ; } return 0; } |
Java
// Java program to find the number of ordered // pairs such that a * p + b * q = N // where p and q are primes public class GFG { final static int size = 10001 ; static int prime[] = new int [size]; static int freq[] = new int [size]; // Sieve of eratosthenes // to store the prime numbers // and their frequency in form a*p+b*q static void sieve( int a, int b) { prime[ 1 ] = 1 ; // Performing Sieve of Eratosthenes // to find the prime numbers unto 10001 for ( int i = 2 ; i * i < size; i++) { if (prime[i] == 0 ) { for ( int j = i * 2 ; j < size; j += i) prime[j] = 1 ; } } // Loop to find the number of // ordered pairs for every combination // of the prime numbers for ( int p = 1 ; p < size; p++) { for ( int q = 1 ; q < size; q++) { if (prime[p] == 0 && prime[q] == 0 && a * p + b * q < size) { freq[a * p + b * q]++; } } } } // Driver code public static void main (String[] args) { int queries = 2 , a = 1 , b = 2 ; sieve(a, b); int arr[] = { 15 , 25 }; // Printing the number of ordered pairs // for every query for ( int i = 0 ; i < queries; i++) { System.out.print(freq[arr[i]] + " " ); } } } // This code is contributed by AnkitRai01 |
Python3
# Python3 program to find the number of ordered # pairs such that a * p + b * q = N # where p and q are primes from math import sqrt size = 1000 prime = [ 0 for i in range (size)] freq = [ 0 for i in range (size)] # Sieve of eratosthenes # to store the prime numbers # and their frequency in form a*p+b*q def sieve(a, b): prime[ 1 ] = 1 # Performing Sieve of Eratosthenes # to find the prime numbers unto 10001 for i in range ( 2 , int (sqrt(size)) + 1 , 1 ): if (prime[i] = = 0 ): for j in range (i * 2 , size, i): prime[j] = 1 # Loop to find the number of # ordered pairs for every combination # of the prime numbers for p in range ( 1 , size, 1 ): for q in range ( 1 , size, 1 ): if (prime[p] = = 0 and prime[q] = = 0 and a * p + b * q < size): freq[a * p + b * q] + = 1 # Driver code if __name__ = = '__main__' : queries = 2 a = 1 b = 2 sieve(a, b) arr = [ 15 , 25 ] # Printing the number of ordered pairs # for every query for i in range (queries): print (freq[arr[i]],end = " " ) # This code is contributed by Surendra_Gangwar |
C#
// C# program to find the number of ordered // pairs such that a * p + b * q = N // where p and q are primes using System; class GFG { static int size = 10001; static int []prime = new int [size]; static int []freq = new int [size]; // Sieve of eratosthenes // to store the prime numbers // and their frequency in form a*p+b*q static void sieve( int a, int b) { prime[1] = 1; // Performing Sieve of Eratosthenes // to find the prime numbers unto 10001 for ( int i = 2; i * i < size; i++) { if (prime[i] == 0) { for ( int j = i * 2; j < size; j += i) prime[j] = 1; } } // Loop to find the number of // ordered pairs for every combination // of the prime numbers for ( int p = 1; p < size; p++) { for ( int q = 1; q < size; q++) { if (prime[p] == 0 && prime[q] == 0 && a * p + b * q < size) { freq[a * p + b * q]++; } } } } // Driver code public static void Main ( string [] args) { int queries = 2, a = 1, b = 2; sieve(a, b); int []arr = { 15, 25 }; // Printing the number of ordered pairs // for every query for ( int i = 0; i < queries; i++) { Console.Write(freq[arr[i]] + " " ); } } } // This code is contributed by AnkitRai01 |
Javascript
<script> // JavaScript program to find the number of ordered // pairs such that a * p + b * q = N // where p and q are primes size=10001 prime = Array(size).fill(0); freq = Array(size).fill(0); // Sieve of eratosthenes // to store the prime numbers // and their frequency in form a*p+b*q function sieve(a, b) { prime[1] = 1; // Performing Sieve of Eratosthenes // to find the prime numbers unto 10001 for ( var i = 2; i * i < size; i++) { if (prime[i] == 0) { for ( var j = i * 2; j < size; j += i) prime[j] = 1; } } // Loop to find the number of // ordered pairs for every combination // of the prime numbers for ( var p = 1; p < size; p++) { for ( var q = 1; q < size; q++) { if (prime[p] == 0 && prime[q] == 0 && a * p + b * q < size) { freq[a * p + b * q]++; } } } } // Driver code var queries = 2, a = 1, b = 2; sieve(a, b); var arr = [ 15, 25 ]; // Printing the number of ordered pairs // for every query for ( var i = 0; i < queries; i++) { document.write(freq[arr[i]] + " " ); } </script> |
2 3
Time Complexity: O(N)
Auxiliary Space: O(size)
Contact Us