Given a positive integer n, count distinct number of pairs (x, y) that satisfy following conditions :
- (x + y) is a prime number.
- (x + y) < n
- x != y
- 1 <= x, y
Examples:
Input : n = 6 Output : 3 prime pairs whose sum is less than 6 are: (1,2), (1,4), (2,3) Input : 12 Output : 11 prime pairs whose sum is less than 12 are: (1,2), (1,4), (2,3), (1,6), (2,5), (3,4), (1,10), (2,9), (3,8), (4,7), (5,6)
Approach:
1) Find all prime numbers less than n using Sieve of Sundaram 2) For each prime number p, count distinct pairs that sum up to p. For any odd number n, number of distinct pairs that add upto n are n/2 Since, a prime number is a odd number, the same applies for it too.
Example,
For prime number p = 7
distinct pairs that add upto p: p/2 = 7/2 = 3
The three pairs are (1,6), (2,5), (3,4)
For prime number p = 23
distinct pairs that add upto p: p/2 = 23/2 = 11
C++
// C++ implementation of prime pairs// whose sum is less than n#include <bits/stdc++.h>using namespace std;// Sieve of Sundaram for generating// prime numbers less than nvoid SieveOfSundaram(bool marked[], int nNew){ // Main logic of Sundaram. Mark all numbers // of the form i + j + 2ij as true where // 1 <= i <= j for (int i=1; i<=nNew; i++) for (int j=i; (i + j + 2*i*j) <= nNew; j++) marked[i + j + 2*i*j] = true;}// Returns number of pairs with given conditions.int countPrimePairs(int n){ // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a number // given number x. Since we want primes smaller // than n, we reduce n to half int nNew = (n-2)/2; // This array is used to separate numbers of // the form i+j+2ij from others where // 1 <= i <= j bool marked[nNew + 1]; // Initialize all elements as not marked memset(marked, false, sizeof(marked)); SieveOfSundaram(marked, nNew); int count = 0, prime_num; // Find primes. Primes are of the form // 2*i + 1 such that marked[i] is false. for (int i=1; i<=nNew; i++) { if (marked[i] == false) { prime_num = 2*i + 1; // For a given prime number p // number of distinct pairs(i,j) // where (i+j) = p are p/2 count = count + (prime_num / 2); } } return count;}// Driver program to test aboveint main(void){ int n = 12; cout << "Number of prime pairs: " << countPrimePairs(n); return 0;} |
Java
// Java implementation of prime pairs // whose sum is less than n class GFG{ // Sieve of Sundaram for generating // prime numbers less than n static void SieveOfSundaram(boolean marked[], int nNew) { // Main logic of Sundaram. Mark all numbers // of the form i + j + 2ij as true where // 1 <= i <= j for (int i = 1; i <= nNew; i++) for (int j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true; } // Returns number of pairs with given conditions. static int countPrimePairs(int n) { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a number // given number x. Since we want primes smaller // than n, we reduce n to half int nNew = (n - 2) / 2; // This array is used to separate numbers of // the form i+j+2ij from others where // 1 <= i <= j // Initialize all elements as not marked boolean marked[]=new boolean[nNew + 1]; SieveOfSundaram(marked, nNew); int count = 0, prime_num; // Find primes. Primes are of the form // 2*i + 1 such that marked[i] is false. for (int i = 1; i <= nNew; i++) { if (marked[i] == false) { prime_num = 2 * i + 1; // For a given prime number p // number of distinct pairs(i, j) // where (i + j) = p are p/2 count = count + (prime_num / 2); } } return count; } // Driver codepublic static void main (String[] args) { int n = 12; System.out.println("Number of prime pairs: " + countPrimePairs(n)); } }// This code is contributed by mits |
Python3
# Python3 implementation of prime pairs# whose sum is less than n# Sieve of Sundaram for generating# prime numbers less than ndef SieveOfSundaram(marked, nNew): # Main logic of Sundaram. Mark all numbers # of the form i + j + 2ij as true where # 1 <= i <= j for i in range(1, nNew + 1): for j in range(i, nNew): if i + j + 2 * i * j > nNew: break marked[i + j + 2 * i * j] = True# Returns number of pairs with given conditions.def countPrimePairs(n): # In general Sieve of Sundaram, produces # primes smaller than (2*x + 2) for a number # given number x. Since we want primes smaller # than n, we reduce n to half nNew = (n - 2) // 2 # This array is used to separate numbers # of the form i+j+2ij from others where # 1 <= i <= j marked = [ False for i in range(nNew + 1)] SieveOfSundaram(marked, nNew) count, prime_num = 0, 0 # Find primes. Primes are of the form # 2*i + 1 such that marked[i] is false. for i in range(1, nNew + 1): if (marked[i] == False): prime_num = 2 * i + 1 # For a given prime number p # number of distinct pairs(i,j) # where (i+j) = p are p/2 count = count + (prime_num // 2) return count# Driver Coden = 12print("Number of prime pairs: ", countPrimePairs(n))# This code is contributed by Mohit kumar 29 |
C#
// C# implementation of prime pairs // whose sum is less than n using System;class GFG{ // Sieve of Sundaram for generating // prime numbers less than n static void SieveOfSundaram(bool[] marked, int nNew) { // Main logic of Sundaram. Mark all numbers // of the form i + j + 2ij as true where // 1 <= i <= j for (int i = 1; i <= nNew; i++) for (int j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true; } // Returns number of pairs with given conditions. static int countPrimePairs(int n) { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than n, we reduce n to half int nNew = (n - 2) / 2; // This array is used to separate numbers // of the form i+j+2ij from others where // 1 <= i <= j // Initialize all elements as not marked bool[] marked = new bool[nNew + 1]; SieveOfSundaram(marked, nNew); int count = 0, prime_num; // Find primes. Primes are of the form // 2*i + 1 such that marked[i] is false. for (int i = 1; i <= nNew; i++) { if (marked[i] == false) { prime_num = 2 * i + 1; // For a given prime number p // number of distinct pairs(i, j) // where (i + j) = p are p/2 count = count + (prime_num / 2); } } return count; } // Driver codepublic static void Main () { int n = 12; Console.WriteLine("Number of prime pairs: " + countPrimePairs(n)); } }// This Code is Contribute by Mukul Singh. |
PHP
<?php// PHP implementation of prime pairs// whose sum is less than n// Sieve of Sundaram for generating// prime numbers less than nfunction SieveOfSundaram(&$marked, $nNew){ // Main logic of Sundaram. Mark all // numbers of the form i + j + 2ij // as true where 1 <= i <= j for ($i = 1; $i <= $nNew; $i++) for ($j = $i; ($i + $j + 2 * $i * $j) <= $nNew; $j++) $marked[$i + $j + 2 * $i * $j] = true;}// Returns number of pairs with// given conditions.function countPrimePairs($n){ // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a // number given number x. Since we want // primes smaller than n, we reduce n to half $nNew = ($n - 2) / 2; // This array is used to separate numbers // of the form i+j+2ij from others where // 1 <= i <= j $marked = array_fill(0, $nNew + 1, false); SieveOfSundaram($marked, $nNew); $count = 0; // Find primes. Primes are of the form // 2*i + 1 such that marked[i] is false. for ($i = 1; $i <= $nNew; $i++) { if ($marked[$i] == false) { $prime_num = 2 * $i + 1; // For a given prime number p // number of distinct pairs(i,j) // where (i+j) = p are p/2 $count = $count + (int)($prime_num / 2); } } return $count;}// Driver Code$n = 12;echo "Number of prime pairs: " . countPrimePairs($n);// This code is contributed by // chandan_jnu?> |
Javascript
<script>// Javascript implementation of prime pairs // whose sum is less than n // Sieve of Sundaram for generating // prime numbers less than n function SieveOfSundaram(marked, nNew) { // Main logic of Sundaram. Mark all numbers // of the form i + j + 2ij as true where // 1 <= i <= j for(i = 1; i <= nNew; i++) for(j = i; (i + j + 2 * i * j) <= nNew; j++) marked[i + j + 2 * i * j] = true; } // Returns number of pairs with given conditions. function countPrimePairs(n) { // In general Sieve of Sundaram, produces // primes smaller than (2*x + 2) for a number // given number x. Since we want primes smaller // than n, we reduce n to half var nNew = parseInt((n - 2) / 2); // This array is used to separate numbers of // the form i+j+2ij from others where // 1 <= i <= j // Initialize all elements as not marked marked = Array.from({length: nNew + 1}, (_, i) => false); SieveOfSundaram(marked, nNew); var count = 0, prime_num; // Find primes. Primes are of the form // 2*i + 1 such that marked[i] is false. for(i = 1; i <= nNew; i++) { if (marked[i] == false) { prime_num = 2 * i + 1; // For a given prime number p // number of distinct pairs(i, j) // where (i + j) = p are p/2 count = count + parseInt(prime_num / 2); } } return count; } // Driver codevar n = 12; document.write("Number of prime pairs: " + countPrimePairs(n)); // This code is contributed by Princi Singh </script> |
Output:
Number of prime pairs: 11
Time Complexity: O(N^2), As we are using Sieve of Sundaram, it takes O(N) time.
Auxiliary Space: O(N), We are using an additional boolean array of size N to mark the prime numbers.
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
