Dado un número N, debe imprimir su número primo más cercano. El número primo puede ser menor, igual o mayor que el número dado.
Condición: 1 ≤ N ≤ 100000
Ejemplos:
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).
Acercarse :
- Usando el tamiz de Eratóstenes , almacene todos los números primos en un vector .
- Copie todos los elementos en el vector a la nueva array.
- Use el límite superior para encontrar el límite superior del número dado en una array.
- Como la array ya está ordenada por naturaleza, compare los números indexados anteriores y actuales en una array.
- Devuelve el número con la diferencia más pequeña.
A continuación se muestra la implementación del enfoque.
Java
// Closest Prime Number in Java
import 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));
}
}
Producción
101
Complejidad de tiempo: O(N log(log(N)))
Complejidad espacial: O(N)