Consecutive Prime numbers greater than equal to given number.
Question:
Given a number n, the task is to find two consecutive prime such that the product of these two prime is greater than or equal to n.
Example:
Input: 14
Output: 3 5
Explanation: 3 and 5 are consecutive prime numbers whose product is greater than 14.
Approach:
Suppose n is of the range 10^8 to 10^10. We cannot find out primes using sieve because the range is upto10^10.
We can find the required consecutive primes by doing the following method.
- Find the greatest prime which is less than sqrt(n) and store it in a temporary variable (first).
- Find the smallest prime which is greater than sqrt(n) and store it in a temporary variable(second).
- If the product of first and second is greater than equal to n then print it.
- Else find a prime just greater than second and print it along with second.
Code:
C++
//C++ program for the above approach #include <bits/stdc++.h> #define endl "\n" #define ll long long using namespace std; //Function to check prime. bool is_prime(ll n) { if (n == 1) { return false ; } for (ll i = 2; i <= sqrt (n); i++) { if (n % i == 0) { // It means it is not // a prime return false ; } } // No factor other than 1 // therefore prime number return true ; } //Function to find out the required //consecutive primes. void consecutive_primes( int n) { ll first = -1, second = -1; //Finding first prime just // less than sqrt(n). for (ll i = sqrt (n); i >= 2; i--) { if (is_prime(i)) { first = i; break ; } } // Finding prime just greater //than sqrt(n). for (ll i = sqrt (n) + 1; i <= n / 2; i++) { if (is_prime(i)) { second = i; break ; } } // Product of both prime is greater // than n then print it if (first * second >= n) { cout << first << " " <<second << endl; } // Finding prime greater than second else { for (ll i = second + 1; i <= n; i++) { if (is_prime(i)) { cout << second << " " << i << endl; return ; } } } } //Driver Program int main() { ll n = 14; consecutive_primes(n); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG{ // Function to check prime. static boolean is_prime( long n) { if (n == 1 ) { return false ; } for ( long i = 2 ; i <= ( long )Math.sqrt(n); i++) { if (n % i == 0 ) { // It means it is not // a prime return false ; } } // No factor other than 1 // therefore prime number return true ; } // Function to find out the required // consecutive primes. static void consecutive_primes( long n) { long first = - 1 , second = - 1 ; // Finding first prime just // less than sqrt(n). for ( long i = ( long )Math.sqrt(n); i >= 2 ; i--) { if (is_prime(i)) { first = i; break ; } } // Finding prime just greater // than sqrt(n). for ( long i = ( long )Math.sqrt(n) + 1 ; i <= n / 2 ; i++) { if (is_prime(i)) { second = i; break ; } } // Product of both prime is greater // than n then print it if (first * second >= n) { System.out.println(first + " " + second); } // Finding prime greater than second else { for ( long i = second + 1 ; i <= n; i++) { if (is_prime(i)) { System.out.println(second + " " + i); return ; } } } } // Driver code public static void main(String args[]) { long n = 14 ; consecutive_primes(n); } } // This code is contributed by splevel62 |
Python3
#python 3 program for the above approach #Function to check prime. from math import sqrt def is_prime(n): if (n = = 1 ): return False for i in range ( 2 , int (sqrt(n)) + 1 , 1 ): if (n % i = = 0 ): # It means it is not # a prime return False # No factor other than 1 # therefore prime number return True # Function to find out the required # consecutive primes. def consecutive_primes(n): first = - 1 second = - 1 # Finding first prime just # less than sqrt(n). i = int (sqrt(n)) while (i > = 2 ): if (is_prime(i)): first = i break i - = 1 # Finding prime just greater #than sqrt(n). for i in range ( int (sqrt(n)) + 1 ,n / / 2 + 1 , 1 ): if (is_prime(i)): second = i break # Product of both prime is greater # than n then print it if (first * second > = n): print (first,second) # Finding prime greater than second else : for i in range (second + 1 ,n + 1 , 1 ): if (is_prime(i)): print (second,i) return # Driver Program if __name__ = = '__main__' : n = 14 consecutive_primes(n) # This code is contributed by SURENDRA_GANGWAR. |
C#
// C# program for the above approach using System; class GFG { // Function to check prime. static bool is_prime( long n) { if (n == 1) { return false ; } for ( long i = 2; i <= ( long )Math.Sqrt(n); i++) { if (n % i == 0) { // It means it is not // a prime return false ; } } // No factor other than 1 // therefore prime number return true ; } // Function to find out the required // consecutive primes. static void consecutive_primes( long n) { long first = -1, second = -1; // Finding first prime just // less than sqrt(n). for ( long i = ( long )Math.Sqrt(n); i >= 2; i--) { if (is_prime(i)) { first = i; break ; } } // Finding prime just greater // than sqrt(n). for ( long i = ( long )Math.Sqrt(n) + 1; i <= n / 2; i++) { if (is_prime(i)) { second = i; break ; } } // Product of both prime is greater // than n then print it if (first * second >= n) { Console.WriteLine(first + " " + second); } // Finding prime greater than second else { for ( long i = second + 1; i <= n; i++) { if (is_prime(i)) { Console.WriteLine(second + " " + i); return ; } } } } // Driver Program public static void Main() { long n = 14; consecutive_primes(n); } } // This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the above approach // Function to check prime. function is_prime(n) { if (n == 1) { return false ; } for ( var i = 2; i <= parseInt(Math.sqrt(n)); i++) { if (n % i == 0) { // It means it is not // a prime return false ; } } // No factor other than 1 // therefore prime number return true ; } // Function to find out the required // consecutive primes. function consecutive_primes(n) { var first = -1, second = -1; // Finding first prime just // less than sqrt(n). for ( var i = parseInt(Math.sqrt(n)); i >= 2; i--) { if (is_prime(i)) { first = i; break ; } } // Finding prime just greater // than sqrt(n). for ( var i = parseInt(Math.sqrt(n)) + 1; i <= parseInt(n / 2); i++) { if (is_prime(i)) { second = i; break ; } } // Product of both prime is greater // than n then print it if (first * second >= n) { document.write(first + " " + second); } // Finding prime greater than second else { for ( var i = second + 1; i <= n; i++) { if (is_prime(i)) { document.write(second + " " + i); return ; } } } } // Driver code var n = 14; consecutive_primes(n); // This code is contributed by 29AjayKumar </script> |
Output
3 5
Time Complexity: O(sqrt(n))
Contact Us