Twin Prime Numbers between 1 and n
Given an integer n. we need to print all twin prime number pairs between 1 to n. A Twin prime are those numbers which are prime and having a difference of two ( 2 ) between the two prime numbers. In other words, a twin prime is a prime that has a prime gap of two.
Sometimes the term twin prime is used for a pair of twin primes; an alternative name for this is prime twin or prime pair. Usually, the pair (2, 3) is not considered to be a pair of twin primes. Since 2 is the only even prime, this pair is the only pair of prime numbers that differ by one; thus twin primes are as closely spaced as possible for any other two primes.
The first few twin prime pairs are :
(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139), …etc.
FACT: There are 409 Twin primes below 10, 000.
Examples:
Input : n = 15
Output : (3, 5), (5, 7), (11, 13)Input : 25
Output : (3, 5), (5, 7), (11, 13), (17, 19)
Approach:
Using Sieve of Eratosthenes find the list of all primes smaller than or equal to n and then iterate list again till n and just checks the ith number and check its (i+2)th number if both are prime then print both the numbers else proceed to next number to find Twin prime.
C++
// C++ program print all twin primes // using Sieve of Eratosthenes. #include <bits/stdc++.h> using namespace std; void printTwinPrime( int n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as true. // A value in prime[i] will finally be false // if i is Not a prime, else true. bool prime[n + 1]; memset (prime, true , sizeof (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 ; } } // to check for twin prime numbers // display the twin primes for ( int p = 2; p <= n - 2; p++) if (prime[p] && prime[p + 2]) cout << "(" << p << ", " << p + 2 << ")" ; } // Driver Program to test above function int main() { int n = 25; // Calling the function printTwinPrime(n); return 0; } |
Java
// Java program to print all Twin Prime // Numbers using Sieve of Eratosthenes import java.io.*; class GFG { static void printTwinPrime( int n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as // true. A value in prime[i] will // finally be false if i is Not a // prime, else true. boolean prime[] = new boolean [n + 1 ]; for ( int i = 0 ; i <= n; i++) prime[i] = true ; 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 ; } } // to check for twin prime numbers // display th twin prime for ( int i = 2 ; i <= n - 2 ; i++) { if (prime[i] == true && prime[i + 2 ] == true ) // Display the result System.out.print( " (" + i + ", " + (i + 2 ) + ")" ); } } // Driver Program to test above function public static void main(String args[]) { int n = 25 ; printTwinPrime(n); } } |
Python
# Python program to illustrate... # To print total number of twin prime # using Sieve of Eratosthenes def printTwinPrime(n): # Create a boolean array "prime[0..n]" # and initialize all entries it as # true. A value in prime[i] will # finally be false if i is Not a prime, # else true. prime = [ True for i in range (n + 2 )] p = 2 while (p * p < = n + 1 ): # If prime[p] is not changed, # then it is a prime if (prime[p] = = True ): # Update all multiples of p for i in range (p * 2 , n + 2 , p): prime[i] = False p + = 1 # check twin prime numbers # display the twin prime numbers for p in range ( 2 , n - 1 ): if prime[p] and prime[p + 2 ]: print ( "(" ,p, "," , (p + 2 ), ")" ,end = '') # driver program if __name__ = = '__main__' : # static input n = 25 # Calling the function printTwinPrime(n) |
C#
// C# program to illustrate.. // print all twin primes // Using Sieve of Eratosthenes using System; public class GFG { public static void printtwinprime( int n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as // true. A value in prime[i] will // finally be false if i is Not a // prime, else true. bool [] prime = new bool [n + 1]; for ( int i = 0; i < n + 1; i++) prime[i] = true ; 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 ; } } // check for twin prime numbers // To display th result for ( int i = 2; i <= n - 2; i++) { if (prime[i] == true && prime[i + 2] == true ) Console.Write( " (" + i + ", " + (i + 2) + ")" ); } } // Driver Code public static void Main() { // static input int n = 25; // calling the function printtwinprime(n); } } |
PHP
<?php // PHP program to print // all twin primes using // Sieve of Eratosthenes. function printTwinPrime( $n ) { // Create a boolean array // "prime[0..n]" and // initialize all entries // it as true. A value in // prime[i] will finally be // false if i is Not a prime, // else true. $prime = array_fill (0, $n + 1, true); 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; } } // to check for twin // prime numbers display // the twin primes for ( $p = 2; $p <= $n - 2; $p ++) if ( $prime [ $p ] && $prime [ $p + 2]) echo "(" . $p . ", " . ( $p + 2). ")" ; } // Driver Code $n = 25; // Calling the function printTwinPrime( $n ); // This code is contributed by mits. ?> |
Javascript
<script> // JavaScript program to print all Twin Prime // Numbers using Sieve of Eratosthenes function printTwinPrime(n) { // Create a boolean array "prime[0..n]" // and initialize all entries it as // true. A value in prime[i] will // finally be false if i is Not a // prime, else true. let prime = []; for (let i = 0; i <= n; i++) prime[i] = true ; 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 ; } } // to check for twin prime numbers // display th twin prime for (let i = 2; i <= n - 2; i++) { if (prime[i] == true && prime[i + 2] == true ) // Display the result document.write( " (" + i + ", " + (i + 2) + ")" ); } } // Driver program let n = 25; printTwinPrime(n); // This code is contributed by susmitakundugoaldanga. </script> |
(3, 5)(5, 7)(11, 13)(17, 19)
Time Complexity: O(n*log(log(n)))
Auxiliary Space: O(n)
Contact Us