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 numbervoid 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 tripletsvoid 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 numberdef 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 tripletsdef 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 coden = 25printPrimeTriplets(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 numberstatic 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 tripletsstatic 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 Codepublic 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 tripletsfunction 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 tripletsfunction 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 Codelet 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)
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!
