Given a number N, you have to print its closest prime number. The prime number can be lesser, equal, or greater than the given number.
Condition: 1 ≤ N ≤ 100000
Examples:
Input : 16 Output: 17 Explanation: The two nearer prime number of 16 are 13 and 17. But among these, 17 is the closest(As its distance is only 1(17-16) from the given number). Input : 97 Output : 97 Explanation : The closest prime number in this case is the given number number itself as the distance is 0 (97-97).
Approach :
- Using Sieve of Eratosthenes store all prime numbers in a Vector.
- Copy all elements in vector to the new array.
- Use the upper bound to find the upper bound of the given number in an array.
- As the array is already sorted in nature, compare previous and current indexed numbers in an array.
- Return number with the smallest difference.
Below is the implementation of the approach.
C++
#include <iostream>#include <vector>using namespace std;const int MAX = 100005;vector<int> primeNumber;// Sieve of Eratosthenes algorithm to find all prime numbers up to MAXvoid sieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize all entries as true. // A value in prime[i] will finally be false if i is not a prime, else true. bool prime[MAX + 1]; for (int i = 0; i <= MAX; i++) { prime[i] = true; } // Update all multiples of p for (int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { for (int i = p * p; i <= MAX; i += p) { prime[i] = false; } } } // Add all prime numbers to the vector for (int i = 2; i <= MAX; i++) { if (prime[i] == true) { primeNumber.push_back(i); } }}// Binary search to find the index of the smallest element greater than numberint upper_bound(vector<int> arr, int low, int high, int number) { // Base case if (low > high) { return low; } // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than or equal to number, search in the right subarray if (arr[mid] <= number) { return upper_bound(arr, mid + 1, high, number); } // If arr[mid] is greater than number, search in the left subarray return upper_bound(arr, low, mid - 1, number);}// Function to find the closest prime number to a given numberint closestPrime(int number) { // Handle special case of number 1 explicitly if (number == 1) { return 2; } else { // Generate all prime numbers using Sieve of Eratosthenes algorithm sieveOfEratosthenes(); // Convert vector to array for binary search int n = primeNumber.size(); int arr[n]; for (int i = 0; i < n; i++) { arr[i] = primeNumber[i]; } // Find the index of the smallest element greater than number int index = upper_bound(primeNumber, 0, n, number); // Check if the current element or the previous element is the closest if (arr[index] == number || arr[index - 1] == number) { return number; } else if (abs(arr[index] - number) < abs(arr[index - 1] - number)) { return arr[index]; } else { return arr[index - 1]; } }}// Driver program to test the above functionint main() { int number = 100; cout << closestPrime(number) << endl; return 0;} |
Java
// Closest Prime Number in Javaimport java.util.*;import java.lang.*;public class GFG { static int max = 100005; static Vector<Integer> primeNumber = new Vector<>(); static void sieveOfEratosthenes() { // 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[max + 1]; for (int i = 0; i <= max; i++) prime[i] = true; for (int p = 2; p * p <= max; 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 * p; i <= max; i += p) prime[i] = false; } } // Print all prime numbers for (int i = 2; i <= max; i++) { if (prime[i] == true) primeNumber.add(i); } } static int upper_bound(Integer arr[], int low, int high, int X) { // Base Case if (low > high) return low; // Find the middle index int mid = low + (high - low) / 2; // If arr[mid] is less than // or equal to X search in // right subarray if (arr[mid] <= X) { return upper_bound(arr, mid + 1, high, X); } // If arr[mid] is greater than X // then search in left subarray return upper_bound(arr, low, mid - 1, X); } public static int closetPrime(int number) { // We will handle it (for number = 1) explicitly // as the lower/left number of 1 can give us // negative index which will cost Runtime Error. if (number == 1) return 2; else { // calling sieve of eratosthenes to // fill the array into prime numbers sieveOfEratosthenes(); Integer[] arr = primeNumber.toArray( new Integer[primeNumber.size()]); // searching the index int index = upper_bound(arr, 0, arr.length, number); if (arr[index] == number || arr[index - 1] == number) return number; else if (Math.abs(arr[index] - number) < Math.abs(arr[index - 1] - number)) return arr[index]; else return arr[index - 1]; } } // Driver Program public static void main(String[] args) { int number = 100; System.out.println(closetPrime(number)); }} |
Python3
# python code for the above approachimport bisectimport mathMAX = 100005prime_numbers = []# Sieve of Eratosthenes algorithm to find all prime numbers up to MAXdef sieve_of_eratosthenes(): # Create a boolean array "prime[0..n]" and initialize all entries as true. # A value in prime[i] will finally be false if i is not a prime, else true. prime = [True] * (MAX + 1) # Update all multiples of p for p in range(2, int(math.sqrt(MAX)) + 1): # If prime[p] is not changed, then it is a prime if prime[p]: for i in range(p * p, MAX + 1, p): prime[i] = False # Add all prime numbers to the list for i in range(2, MAX + 1): if prime[i]: prime_numbers.append(i)# Function to find the closest prime number to a given numberdef closest_prime(number): # Handle special case of number 1 explicitly if number == 1: return 2 else: # Generate all prime numbers using Sieve of Eratosthenes algorithm sieve_of_eratosthenes() # Find the index of the smallest element greater than number index = bisect.bisect_left(prime_numbers, number) # Check if the current element or the previous element is the closest if prime_numbers[index] == number or prime_numbers[index - 1] == number: return number elif abs(prime_numbers[index] - number) < abs(prime_numbers[index - 1] - number): return prime_numbers[index] else: return prime_numbers[index - 1]# Driver program to test the above functionif __name__ == '__main__': number = 100 print(closest_prime(number)) |
Javascript
const MAX = 100005;let primeNumber = [];// Sieve of Eratosthenes algorithm to find all prime numbers up to MAXfunction sieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize all entries as true. // A value in prime[i] will finally be false if i is not a prime, else true. let prime = Array(MAX + 1).fill(true); // Update all multiples of p for (let p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { for (let i = p * p; i <= MAX; i += p) { prime[i] = false; } } } // Add all prime numbers to the vector for (let i = 2; i <= MAX; i++) { if (prime[i] == true) { primeNumber.push(i); } }}// Binary search to find the index of the smallest element greater than numberfunction upper_bound(arr, low, high, number) { // Base case if (low > high) { return low; } // Find the middle index let mid = low + Math.floor((high - low) / 2); // If arr[mid] is less than or equal to number, search in the right subarray if (arr[mid] <= number) { return upper_bound(arr, mid + 1, high, number); } // If arr[mid] is greater than number, search in the left subarray return upper_bound(arr, low, mid - 1, number);}// Function to find the closest prime number to a given numberfunction closestPrime(number) { // Handle special case of number 1 explicitly if (number == 1) { return 2; } else { // Generate all prime numbers using Sieve of Eratosthenes algorithm sieveOfEratosthenes(); // Find the index of the smallest element greater than number let index = upper_bound(primeNumber, 0, primeNumber.length, number); // Check if the current element or the previous element is the closest if (primeNumber[index] == number || primeNumber[index - 1] == number) { return number; } else if (Math.abs(primeNumber[index] - number) < Math.abs(primeNumber[index - 1] - number)) { return primeNumber[index]; } else { return primeNumber[index - 1]; } }}// Driver program to test the above functionlet number = 100;console.log(closestPrime(number)); |
C#
//C# code for the above approachusing System;using System.Collections.Generic;public class Program{ const int MAX = 100005; static List<int> prime_numbers = new List<int>(); // Sieve of Eratosthenes algorithm to find all prime numbers up to MAX static void sieve_of_eratosthenes() { // Create a boolean array "prime[0..n]" and initialize all entries as true. // A value in prime[i] will finally be false if i is not a prime, else true. bool[] prime = new bool[MAX + 1]; for (int i = 0; i <= MAX; i++) { prime[i] = true; } // Update all multiples of p for (int p = 2; p <= Math.Sqrt(MAX); p++) { // If prime[p] is not changed, then it is a prime if (prime[p]) { for (int i = p * p; i <= MAX; i += p) { prime[i] = false; } } } // Add all prime numbers to the list for (int i = 2; i <= MAX; i++) { if (prime[i]) { prime_numbers.Add(i); } } } // Function to find the closest prime number to a given number static int closest_prime(int number) { // Handle special case of number 1 explicitly if (number == 1) { return 2; } else { // Generate all prime numbers using Sieve of Eratosthenes algorithm sieve_of_eratosthenes(); // Find the index of the smallest element greater than number int index = prime_numbers.BinarySearch(number); if (index < 0) { index = ~index; } // Check if the current element or the previous element is the closest if (prime_numbers[index] == number || prime_numbers[index - 1] == number) { return number; } else if (Math.Abs(prime_numbers[index] - number) < Math.Abs(prime_numbers[index - 1] - number)) { return prime_numbers[index]; } else { return prime_numbers[index - 1]; } } } // Driver program to test the above function public static void Main() { int number = 100; Console.WriteLine(closest_prime(number)); }}//This code is contributed by shivamsharma215 |
Output
101
Time Complexity: O(N log(log(N)))
Auxiliary Space: O(N)
