Given an integer N, the task is to count the number of distinct prime triplets (a, b, c) from the range [1, N] such that a < b < c ? N and a + b = c.
Note: Two prime tuples are distinct if at least one of the primes present in them are different.
Examples:
Input: N = 6
Output: 1
Explanation: Among numbers in the range [1, 6], the only prime triplet is (2, 3, 5) (Since 2 + 3 = 5).Input: N = 10
Output: 2
Explanation: The distinct prime triplets satisfying the condition are (2, 3, 5), (2, 5, 7).
Approach: The problem can be solved based on the observation stated below:
Observation:
For every prime number p from 1 to N, it is a part of a triplet if and only if it can be represented as a sum of two prime numbers.
Since a prime number is an odd number, it must be equal to the sum of an even number and an odd number.
Hence the only even prime is 2. Therefore, for a prime number p to constitute a unique tuple (2, p-2, p), the number p – 2 must be a prime number.
Follow the steps below to solve the problem:
- Initialize a variable, say count = 0, to store the number of prime triplets.
- Iterate from 1 to N and for each number p, check if this number p and p – 2 are prime or not.
- If they are prime, then increment count by 1.
- Print the value of count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a // number is a prime or not bool isPrime( int N) { if (N <= 1) return false ; for ( int i = 2; i <= sqrt (N); i++) { if (N % i == 0) return false ; } return true ; } // Function to count the number // of valid prime triplets void countPrimeTuples( int N) { // Stores the count // of prime triplets int count = 0; // Iterate from 2 to N and check for each // p, whether p & (p - 2) are prime or not for ( int i = 2; i <= N; i++) { if (isPrime(i) && isPrime(i - 2)) count++; } // Print the count obtained cout << count; } // Driver Code int main() { int N = 6; countPrimeTuples(N); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to check if a // number is a prime or not static boolean isPrime( int N) { if (N <= 1 ) return false ; for ( int i = 2 ; i <= Math.sqrt(N); i++) { if (N % i == 0 ) return false ; } return true ; } // Function to count the number // of valid prime triplets static void countPrimeTuples( int N) { // Stores the count // of prime triplets int count = 0 ; // Iterate from 2 to N and check for each // p, whether p & (p - 2) are prime or not for ( int i = 2 ; i <= N; i++) { if (isPrime(i) && isPrime(i - 2 )) count++; } // Print the count obtained System.out.println(count); } // Driver Code public static void main (String[] args) { int N = 6 ; countPrimeTuples(N); } } // This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach import math # Function to check if a # number is a prime or not def isPrime(N) : if (N < = 1 ) : return False for i in range ( 2 , int (math.sqrt(N) + 1 )): if (N % i = = 0 ) : return False return True # Function to count the number # of valid prime triplets def countPrimeTuples(N) : # Stores the count # of prime triplets count = 0 # Iterate from 2 to N and check for each # p, whether p & (p - 2) are prime or not for i in range ( 2 , N + 1 ): if (isPrime(i) and isPrime(i - 2 )) : count + = 1 # Print count obtained print (count) # Driver Code N = 6 countPrimeTuples(N) # This code is contributed by susmitakundugoaldanga. |
C#
// C# program for the above approach using System; public class GFG { // Function to check if a // number is a prime or not static bool isPrime( int N) { if (N <= 1) return false ; for ( int i = 2; i <= Math.Sqrt(N); i++) { if (N % i == 0) return false ; } return true ; } // Function to count the number // of valid prime triplets static void countPrimeTuples( int N) { // Stores the count // of prime triplets int count = 0; // Iterate from 2 to N and check for each // p, whether p & (p - 2) are prime or not for ( int i = 2; i <= N; i++) { if (isPrime(i) && isPrime(i - 2)) count++; } // Print the count obtained Console.WriteLine(count); } // Driver Code static public void Main () { int N = 6; countPrimeTuples(N); } } // This code is contributed by Dharanendra L V. |
Javascript
<script> // Javascript program for the above approach // Function to check if a // number is a prime or not function isPrime(N) { if (N <= 1) return false ; for (let i = 2; i <= Math.sqrt(N); i++) { if (N % i == 0) return false ; } return true ; } // Function to count the number // of valid prime triplets function countPrimeTuples(N) { // Stores the count // of prime triplets let count = 0; // Iterate from 2 to N and check for each // p, whether p & (p - 2) are prime or not for (let i = 2; i <= N; i++) { if (isPrime(i) && isPrime(i - 2)) count++; } // Print the count obtained document.write(count); } // Driver Code let N = 6; countPrimeTuples(N); // This code is contributed by _saurabh_jaiswal </script> |
1
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!