Prime Triplet
Prime Triplet is a set of three prime numbers of the form (p, p+2, p+6) or (p, p+4, p+6). This is the closest possible grouping of three prime numbers, since one of every three sequential odd numbers is a multiple of three, and hence not prime (except for 3 itself) except (2, 3, 5) and (3, 5, 7).
Examples :
Input : n = 15 Output : 5 7 11 7 11 13 Input : n = 25 Output : 5 7 11 7 11 13 11 13 17 13 17 19 17 19 23
A simple solution is to traverse through all numbers from 1 to n-6. For every number, i check if i, i+2, i+6, or i, i+4, i+6 are primes. If yes, print triplets.
An efficient solution is Sieve of Eratosthenes to first find all prime numbers so that we can quickly check if a number is prime or not.
Below is the implementation of the approach.
C++
// C++ program to find prime triplets smaller // than or equal to n. #include <bits/stdc++.h> using namespace std; // function to detect prime number // here we have used sieve method // to detect prime number void sieve( int n, bool prime[]) { for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p * 2; i <= n; i += p) prime[i] = false ; } } } // function to print prime triplets void printPrimeTriplets( int n) { // Finding all primes from 1 to n bool prime[n + 1]; memset (prime, true , sizeof (prime)); sieve(n, prime); cout << "The prime triplets from 1 to " << n << "are :" << endl; for ( int i = 2; i <= n-6; ++i) { // triplets of form (p, p+2, p+6) if (prime[i] && prime[i + 2] && prime[i + 6]) cout << i << " " << (i + 2) << " " << (i + 6) << endl; // triplets of form (p, p+4, p+6) else if (prime[i] && prime[i + 4] && prime[i + 6]) cout << i << " " << (i + 4) << " " << (i + 6) << endl; } } int main() { int n = 25; printPrimeTriplets(n); return 0; } |
Java
// Java program to find prime triplets // smaller than or equal to n. import java.io.*; import java.util.*; class GFG { // function to detect prime number // here we have used sieve method // to detect prime number static void sieve( int n, boolean prime[]) { for ( int p = 2 ; p * p <= n; p++) { // If prime[p] is not changed, //then it is a prime if (prime[p] == true ) { // Update all multiples of p for ( int i = p * 2 ; i <= n; i += p) prime[i] = false ; } } } // function to print prime triplets static void printPrimeTriplets( int n) { // Finding all primes from 1 to n boolean prime[]= new boolean [n + 1 ]; Arrays.fill(prime, true ); sieve(n, prime); System.out.println( "The prime triplets" + " from 1 to " + n + "are :" ); for ( int i = 2 ; i <= n- 6 ; ++i) { // triplets of form (p, p+2, p+6) if (prime[i] && prime[i + 2 ] && prime[i + 6 ]) System.out.println( i + " " + (i + 2 ) + " " + (i + 6 )); // triplets of form (p, p+4, p+6) else if (prime[i] && prime[i + 4 ] && prime[i + 6 ]) System.out.println(i + " " + (i + 4 ) + " " + (i + 6 )); } } public static void main(String args[]) { int n = 25 ; printPrimeTriplets(n); } } /*This code is contributed by Nikita Tiwari.*/ |
Python3
# Python 3 program to find # prime triplets smaller # than or equal to n. # function to detect prime number # using sieve method # to detect prime number def sieve(n, prime) : p = 2 while (p * p < = n ) : # If prime[p] is not changed # , then it is a prime if (prime[p] = = True ) : # Update all multiples of p i = p * 2 while ( i < = n ) : prime[i] = False i = i + p p = p + 1 # function to print # prime triplets def printPrimeTriplets(n) : # Finding all primes # from 1 to n prime = [ True ] * (n + 1 ) sieve(n, prime) print ( "The prime triplets from 1 to " , n , "are :" ) for i in range ( 2 , n - 6 + 1 ) : # triplets of form (p, p+2, p+6) if (prime[i] and prime[i + 2 ] and prime[i + 6 ]) : print ( i , (i + 2 ) , (i + 6 )) # triplets of form (p, p+4, p+6) elif (prime[i] and prime[i + 4 ] and prime[i + 6 ]) : print (i , (i + 4 ) , (i + 6 )) # Driver code n = 25 printPrimeTriplets(n) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find prime // triplets smaller than or // equal to n. using System; class GFG { // function to detect // prime number static void sieve( int n, bool [] prime) { for ( int p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == false ) { // Update all multiples of p for ( int i = p * 2; i <= n; i += p) prime[i] = true ; } } } // function to print // prime triplets static void printPrimeTriplets( int n) { // Finding all primes // from 1 to n bool [] prime = new bool [n + 1]; sieve(n, prime); Console.WriteLine( "The prime triplets " + "from 1 to " + n + " are :" ); for ( int i = 2; i <= n - 6; ++i) { // triplets of form (p, p+2, p+6) if (!prime[i] && !prime[i + 2] && !prime[i + 6]) Console.WriteLine(i + " " + (i + 2) + " " + (i + 6)); // triplets of form (p, p+4, p+6) else if (!prime[i] && !prime[i + 4] && !prime[i + 6]) Console.WriteLine(i + " " + (i + 4) + " " + (i + 6)); } } // Driver Code public static void Main() { int n = 25; printPrimeTriplets(n); } } // This code is contributed by mits |
PHP
<?php // PHP program to find prime // triplets smaller than or // equal to n. // function to print // prime triplets function printPrimeTriplets( $n ) { // Finding all primes // from 1 to n $prime = array_fill (0, $n + 1, true); // to detect prime number for ( $p = 2; $p * $p <= $n ; $p ++) { // If prime[p] is not changed, // then it is a prime if ( $prime [ $p ] == true) { // Update all multiples of p for ( $i = $p * 2; $i <= $n ; $i += $p ) $prime [ $i ] = false; } } echo "The prime triplets from 1 to " . $n . " are :\n" ; for ( $i = 2; $i <= $n -6; ++ $i ) { // triplets of form (p, p+2, p+6) if ( $prime [ $i ] && $prime [ $i + 2] && $prime [ $i + 6]) echo $i . " " . ( $i + 2) . " " . ( $i + 6) . "\n" ; // triplets of form (p, p+4, p+6) else if ( $prime [ $i ] && $prime [ $i + 4] && $prime [ $i + 6]) echo $i . " " . ( $i + 4) . " " . ( $i + 6) . "\n" ; } } // Driver Code $n = 25; printPrimeTriplets( $n ); // This code is contributed by mits. ?> |
Javascript
<script> // Javascript program to find prime // triplets smaller than or // equal to n. // function to print // prime triplets function printPrimeTriplets(n) { // Finding all primes // from 1 to n let prime = new Array(n + 1).fill( true ); // to detect prime number for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p] == true ) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) prime[i] = false ; } } document.write( "The prime triplets from 1 to " + n + " are :<br>" ); for (let i = 2; i <= n-6; ++i) { // triplets of form (p, p+2, p+6) if (prime[i] && prime[i + 2] && prime[i + 6]) document.write(i + " " + (i + 2) + " " + (i + 6) + "<br>" ); // triplets of form (p, p+4, p+6) else if (prime[i] && prime[i + 4] && prime[i + 6]) document.write(i + " " + (i + 4) + " " + (i + 6) + "<br>" ); } } // Driver Code let n = 25; printPrimeTriplets(n); // This code is contributed by gfgking </script> |
Output :
The prime triplets from 1 to 25 are : 5 7 11 7 11 13 11 13 17 13 17 19 17 19 23
Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)