Given a range [low..high], print the smallest twin numbers in given range (low and high inclusive). Two numbers are twins if they are primes and there difference is 2.
Example:
Input: low = 10, high = 100 Output: Smallest twins in given range: (11, 13) Both 11 and 13 are prime numbers and difference between them is two, therefore twins. And these are the smallest twins in [10..100] Input: low = 50, high = 100 Output: Smallest twins in given range: (59, 61)
A Simple Solution is to start to start from low and for every number x check if x and x + 2 are primes are not. Here x varies from low to high-2.
An Efficient Solution is to use Sieve of Eratosthenes
1) Create a boolean array "prime[0..high]" and initialize all
entries in it as true. A value in prime[i] will finally
be false if i is not a prime number, else true.
2) Run a loop from p = 2 to high.
a) If prime[p] is true, then p is prime. [See this]
b) Mark all multiples of p as not prime in prime[].
3) Run a loop from low to high and print the first twins
using prime[] built in step 2.
Below is the implementation of above idea.
C++
// C++ program to find the smallest twin in given range #include <bits/stdc++.h> using namespace std; void printTwins(int low, int high) { // Create a boolean array "prime[0..high]" 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[high+1], twin = false; memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; // Look for the smallest twin for (int p=2; p<=floor(sqrt(high))+1; p++) { // If p is not marked, then it is a prime if (prime[p]) { // Update all multiples of p for (int i=p*2; i<=high; i += p) prime[i] = false; } } // Now print the smallest twin in range for (int i=low; i<=high; i++) { if (prime[i] && prime[i+2]) { cout << "Smallest twins in given range: (" << i << ", " << i+2 << ")"; twin = true; break; } } if (twin == false) cout << "No such pair exists" <<endl;} // Driver program int main() { printTwins(10, 100); return 0; } |
Java
// Java program to find the smallest twin in given range class GFG { static void printTwins(int low, int high) { // Create a boolean array "prime[0..high]" 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[high + 1], twin = false; for (int i = 0; i < prime.length; i++) { prime[i] = true; } prime[0] = prime[1] = false; // Look for the smallest twin for (int p = 2; p <= Math.floor(Math.sqrt(high)) + 1; p++) { // If p is not marked, then it is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= high; i += p) { prime[i] = false; } } } // Now print the smallest twin in range for (int i = low; i <= high; i++) { if (prime[i] && prime[i + 2]) { int a = i + 2 ; System.out.print("Smallest twins in given range: (" + i + ", " + a + ")"); twin = true; break; } } if (twin == false) { System.out.println("No such pair exists"); } }// Driver program public static void main(String[] args) { printTwins(10, 100); }}// This code contributed by Rajput-Ji |
Python3
# Python3 program to find the smallest # twin in given range import mathdef printTwins(low, high): # Create a boolean array "prime[0..high]" # 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] * (high + 1); twin = False; prime[0] = prime[1] = False; # Look for the smallest twin for p in range(2, int(math.floor( math.sqrt(high)) + 2)): # If p is not marked, then it # is a prime if (prime[p]): # Update all multiples of p for i in range(p * 2, high + 1, p): prime[i] = False; # Now print the smallest twin in range for i in range(low, high + 1): if (prime[i] and prime[i + 2]): print("Smallest twins in given range: (", i, ",", (i + 2), ")"); twin = True; break; if (twin == False): print("No such pair exists");# Driver CodeprintTwins(10, 100); # This code is contributed # by chandan_jnu |
C#
// C# program to find the smallest twin in given range using System; public class GFG { static void printTwins(int low, int high) { // Create a boolean array "prime[0..high]" 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[high + 1]; bool twin = false; for (int i = 0; i < prime.Length; i++) { prime[i] = true; } prime[0] = prime[1] = false; // Look for the smallest twin for (int p = 2; p <= Math.Floor(Math.Sqrt(high)) + 1; p++) { // If p is not marked, then it is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= high; i += p) { prime[i] = false; } } } // Now print the smallest twin in range for (int i = low; i <= high; i++) { if (prime[i] && prime[i + 2]) { int a = i + 2 ; Console.Write("Smallest twins in given range: (" + i + ", " + a + ")"); twin = true; break; } } if (twin == false) { Console.WriteLine("No such pair exists"); } } // Driver program public static void Main() { printTwins(10, 100); }}//this code contributed by Rajput-Ji |
PHP
<?php// PHP program to find the smallest // twin in given range function printTwins($low, $high) { // Create a boolean array "prime[0..high]" // 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, $high + 1, true); $twin = false; $prime[0] = $prime[1] = false; // Look for the smallest twin for ($p = 2; $p <= floor(sqrt($high)) + 1; $p++) { // If p is not marked, then it is a prime if ($prime[$p]) { // Update all multiples of p for ($i = $p * 2; $i <= $high; $i += $p) $prime[$i] = false; } } // Now print the smallest twin in range for ($i = $low; $i <= $high; $i++) { if ($prime[$i] && $prime[$i + 2]) { print("Smallest twins in given range: ($i, ". ($i + 2). ")"); $twin = true; break; } } if ($twin == false) print("No such pair exists\n");} // Driver CodeprintTwins(10, 100); // This code is contributed by mits?> |
Javascript
<script>// Javascript program to find the // smallest twin in given range function printTwins(low, high){ // Create a boolean array "prime[0..high]" // and initialize all entries it as true. // A value in prime[i] will finally // be false if i is Not a prime, else true. var prime = Array.from({length: high + 1}, (_, i) => 0); var twin = false; for(i = 0; i < prime.length; i++) { prime[i] = true; } prime[0] = prime[1] = false; // Look for the smallest twin for(p = 2; p <= Math.floor(Math.sqrt(high)) + 1; p++) { // If p is not marked, then it is a prime if (prime[p]) { // Update all multiples of p for(i = p * 2; i <= high; i += p) { prime[i] = false; } } } // Now print the smallest twin in range for(i = low; i <= high; i++) { if (prime[i] && prime[i + 2]) { var a = i + 2 ; document.write("Smallest twins in " + "given range: (" + i + ", " + a + ")"); twin = true; break; } } if (twin == false) { document.write("No such pair exists"); }}// Driver codeprintTwins(10, 100);// This code is contributed by shikhasingrajput </script> |
Output:
Smallest twins in given range: (11, 13)
Thanks to Utkarsh Trivedi for suggesting this solution.
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!
