Primo más cercano menor que el número dado n

¿Te dan un número n (3 <= n < 10^6) y tienes que encontrar el primo más cercano menor que n?

Ejemplos: 

Input : n = 10
Output: 7

Input : n = 17
Output: 13

Input : n = 30
Output: 29 

Una solución simple para este problema es iterar de n-1 a 2, y para cada número, verificar si es primo . Si es primo, devuélvalo y rompa el bucle. Esta solución se ve bien si solo hay una consulta. Pero no es eficiente si hay múltiples consultas para diferentes valores de n.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return nearest prime number
int prime(int n)
{
    // All prime numbers are odd except two
    if (n & 1)
        n -= 2;
    else
        n--;
 
    int i, j;
    for (i = n; i >= 2; i -= 2) {
        if (i % 2 == 0)
            continue;
        for (j = 3; j <= sqrt(i); j += 2) {
            if (i % j == 0)
                break;
        }
        if (j > sqrt(i))
            return i;
    }
    // It will only be executed when n is 3
    return 2;
}
 
// Driver Code
int main()
{
    int n = 17;
    cout << prime(n);
    return 0;
}

// C program for the above approach
#include <math.h>
#include <stdio.h>
 
// Function to return nearest prime number
int prime(int n)
{
 
    // All prime numbers are odd except two
    if (n & 1)
        n -= 2;
    else
        n--;
 
    int i, j;
    for (i = n; i >= 2; i -= 2) {
        if (i % 2 == 0)
            continue;
        for (j = 3; j <= sqrt(i); j += 2) {
            if (i % j == 0)
                break;
        }
        if (j > sqrt(i))
            return i;
    }
 
    // It will only be executed when n is 3
    return 2;
}
 
// Driver Code
int main()
{
    int n = 17;
    printf("%d", prime(n));
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

// Java program for the above approach
 
import java.io.*;
 
class GFG {
 
    // Function to return nearest prime number
    static int prime(int n)
    {
 
        // All prime numbers are odd except two
        if (n % 2 != 0)
            n -= 2;
        else
            n--;
 
        int i, j;
        for (i = n; i >= 2; i -= 2) {
            if (i % 2 == 0)
                continue;
            for (j = 3; j <= Math.sqrt(i); j += 2) {
                if (i % j == 0)
                    break;
            }
            if (j > Math.sqrt(i))
                return i;
        }
 
        // It will only be executed when n is 3
        return 2;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 17;
        System.out.print(prime(n));
    }
}
 
// This code is contributed by subham348.

# Python program for the above approach
 
# Function to return nearest prime number
from math import floor, sqrt
 
def prime(n):
     
    # All prime numbers are odd except two
    if (n & 1):
        n -= 2
    else:
        n -= 1
     
    i,j = 0,3
 
    for i in range(n, 2, -2):
 
        if(i % 2 == 0):
            continue
 
        while(j <= floor(sqrt(i)) + 1):
            if (i % j == 0):
                break
            j += 2
 
        if (j > floor(sqrt(i))):
            return i
 
    # It will only be executed when n is 3
    return 2
 
# Driver Code
n = 17
 
print(prime(n))
 
# This code is contributed by shinjanpatra

// C# program for the above approach
using System;
 
class GFG
{
 
    // Function to return nearest prime number
    static int prime(int n)
    {
 
        // All prime numbers are odd except two
        if (n % 2 != 0)
            n -= 2;
        else
            n--;
 
        int i, j;
        for (i = n; i >= 2; i -= 2) {
            if (i % 2 == 0)
                continue;
            for (j = 3; j <= Math.Sqrt(i); j += 2) {
                if (i % j == 0)
                    break;
            }
            if (j > Math.Sqrt(i))
                return i;
        }
 
        // It will only be executed when n is 3
        return 2;
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 17;
        Console.Write(prime(n));
    }
}
 
// This code is contributed by subham348.

<script>
 
// Javascript program for the above approach
 
// Function to return nearest prime number
function prime(n)
{
     
    // All prime numbers are odd except two
    if (n & 1)
        n -= 2;
    else
        n--;
 
    let i, j;
    for(i = n; i >= 2; i -= 2)
    {
        if (i % 2 == 0)
            continue;
        for(j = 3; j <= Math.sqrt(i); j += 2)
        {
            if (i % j == 0)
                break;
        }
        if (j > Math.sqrt(i))
            return i;
    }
 
    // It will only be executed when n is 3
    return 2;
}
 
// Driver Code
let n = 17;
 
document.write(prime(n));
 
// This code is contributed by souravmahato348
 
</script>

13

Una solución eficiente para este problema es generar todos los números primos menores que 10 ^ 6 usando Sieve of Sundaram y almacenarlos en una array en orden creciente. Ahora aplique la búsqueda binaria modificada para buscar el primo más cercano menor que n. La complejidad temporal de esta solución es O(n log n + log n) = O(n log n).

// C++ program to find the nearest prime to n.
#include<bits/stdc++.h>
#define MAX 1000000
using namespace std;
 
// array to store all primes less than 10^6
vector<int> primes;
 
// Utility function of Sieve of Sundaram
void Sieve()
{
    int n = MAX;
 
    // In general Sieve of Sundaram, produces primes
    // smaller than (2*x + 2) for a number given
    // number x
    int nNew = sqrt(n);
 
    // This array is used to separate numbers of the
    // form i+j+2ij from others where  1 <= i <= j
    int marked[n/2+500] = {0};
 
    // eliminate indexes which does not produce primes
    for (int i=1; i<=(nNew-1)/2; i++)
        for (int j=(i*(i+1))<<1; j<=n/2; j=j+2*i+1)
            marked[j] = 1;
 
    // Since 2 is a prime number
    primes.push_back(2);
 
    // Remaining primes are of the form 2*i + 1 such
    // that marked[i] is false.
    for (int i=1; i<=n/2; i++)
        if (marked[i] == 0)
            primes.push_back(2*i + 1);
}
 
// modified binary search to find nearest prime less than N
int binarySearch(int left,int right,int n)
{
    if (left<=right)
    {
        int mid = (left + right)/2;
 
        // base condition is, if we are reaching at left
        // corner or right corner of primes[] array then
        // return that corner element because before or
        // after that we don't have any prime number in
        // primes array
        if (mid == 0 || mid == primes.size()-1)
            return primes[mid];
 
        // now if n is itself a prime so it will be present
        // in primes array and here we have to find nearest
        // prime less than n so we will return primes[mid-1]
        if (primes[mid] == n)
            return primes[mid-1];
 
        // now if primes[mid]<n and primes[mid+1]>n that
        // mean we reached at nearest prime
        if (primes[mid] < n && primes[mid+1] > n)
            return primes[mid];
        if (n < primes[mid])
            return binarySearch(left, mid-1, n);
        else
            return binarySearch(mid+1, right, n);
    }
    return 0;
}
 
// Driver program to run the case
int main()
{
    Sieve();
    int n = 17;
    cout << binarySearch(0, primes.size()-1, n);
    return 0;
}

// Java program to find the nearest prime to n.
import java.util.*;
 
class GFG
{
     
static int MAX=1000000;
 
// array to store all primes less than 10^6
static ArrayList<Integer> primes = new ArrayList<Integer>();
 
// Utility function of Sieve of Sundaram
static void Sieve()
{
    int n = MAX;
 
    // In general Sieve of Sundaram, produces primes
    // smaller than (2*x + 2) for a number given
    // number x
    int nNew = (int)Math.sqrt(n);
 
    // This array is used to separate numbers of the
    // form i+j+2ij from others where 1 <= i <= j
    int[] marked = new int[n / 2 + 500];
 
    // eliminate indexes which does not produce primes
    for (int i = 1; i <= (nNew - 1) / 2; i++)
        for (int j = (i * (i + 1)) << 1;
                j <= n / 2; j = j + 2 * i + 1)
            marked[j] = 1;
 
    // Since 2 is a prime number
    primes.add(2);
 
    // Remaining primes are of the form 2*i + 1 such
    // that marked[i] is false.
    for (int i = 1; i <= n / 2; i++)
        if (marked[i] == 0)
            primes.add(2 * i + 1);
}
 
// modified binary search to find nearest prime less than N
static int binarySearch(int left,int right,int n)
{
    if (left <= right)
    {
        int mid = (left + right) / 2;
 
        // base condition is, if we are reaching at left
        // corner or right corner of primes[] array then
        // return that corner element because before or
        // after that we don't have any prime number in
        // primes array
        if (mid == 0 || mid == primes.size() - 1)
            return primes.get(mid);
 
        // now if n is itself a prime so it will be present
        // in primes array and here we have to find nearest
        // prime less than n so we will return primes[mid-1]
        if (primes.get(mid) == n)
            return primes.get(mid - 1);
 
        // now if primes[mid]<n and primes[mid+1]>n that
        // mean we reached at nearest prime
        if (primes.get(mid) < n && primes.get(mid + 1) > n)
            return primes.get(mid);
        if (n < primes.get(mid))
            return binarySearch(left, mid - 1, n);
        else
            return binarySearch(mid + 1, right, n);
    }
    return 0;
}
 
// Driver code
public static void main (String[] args)
{
    Sieve();
    int n = 17;
    System.out.println(binarySearch(0,
                        primes.size() - 1, n));
}
}
 
// This code is contributed by mits

# Python3 program to find the nearest
# prime to n.
import math
MAX = 10000;
 
# array to store all primes less
# than 10^6
primes = [];
 
# Utility function of Sieve of Sundaram
def Sieve():
 
    n = MAX;
 
    # In general Sieve of Sundaram, produces
    # primes smaller than (2*x + 2) for a
    # number given number x
    nNew = int(math.sqrt(n));
 
    # This array is used to separate numbers
    # of the form i+j+2ij from others where
    # 1 <= i <= j
    marked = [0] * (int(n / 2 + 500));
 
    # eliminate indexes which does not
    # produce primes
    for i in range(1, int((nNew - 1) / 2) + 1):
        for j in range(((i * (i + 1)) << 1),
                        (int(n / 2) + 1), (2 * i + 1)):
            marked[j] = 1;
 
    # Since 2 is a prime number
    primes.append(2);
 
    # Remaining primes are of the form
    # 2*i + 1 such that marked[i] is false.
    for i in range(1, int(n / 2) + 1):
        if (marked[i] == 0):
            primes.append(2 * i + 1);
 
# modified binary search to find nearest
# prime less than N
def binarySearch(left, right, n):
    if (left <= right):
        mid = int((left + right) / 2);
 
        # base condition is, if we are reaching
        # at left corner or right corner of
        # primes[] array then return that corner
        # element because before or after that
        # we don't have any prime number in
        # primes array
        if (mid == 0 or mid == len(primes) - 1):
            return primes[mid];
 
        # now if n is itself a prime so it will
        # be present in primes array and here
        # we have to find nearest prime less than
        # n so we will return primes[mid-1]
        if (primes[mid] == n):
            return primes[mid - 1];
 
        # now if primes[mid]<n and primes[mid+1]>n
        # that means we reached at nearest prime
        if (primes[mid] < n and primes[mid + 1] > n):
            return primes[mid];
        if (n < primes[mid]):
            return binarySearch(left, mid - 1, n);
        else:
            return binarySearch(mid + 1, right, n);
 
    return 0;
 
# Driver Code
Sieve();
n = 17;
print(binarySearch(0, len(primes) - 1, n));
     
# This code is contributed by chandan_jnu

// C# program to find the nearest prime to n.
using System;
using System.Collections;
class GFG
{
     
static int MAX = 1000000;
 
// array to store all primes less than 10^6
static ArrayList primes = new ArrayList();
 
// Utility function of Sieve of Sundaram
static void Sieve()
{
    int n = MAX;
 
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a
    // number given number x
    int nNew = (int)Math.Sqrt(n);
 
    // This array is used to separate numbers of the
    // form i+j+2ij from others where 1 <= i <= j
    int[] marked = new int[n / 2 + 500];
 
    // eliminate indexes which does not produce primes
    for (int i = 1; i <= (nNew - 1) / 2; i++)
        for (int j = (i * (i + 1)) << 1;
                 j <= n / 2; j = j + 2 * i + 1)
            marked[j] = 1;
 
    // Since 2 is a prime number
    primes.Add(2);
 
    // Remaining primes are of the form 2*i + 1
    // such that marked[i] is false.
    for (int i = 1; i <= n / 2; i++)
        if (marked[i] == 0)
            primes.Add(2 * i + 1);
}
 
// modified binary search to find
// nearest prime less than N
static int binarySearch(int left, int right, int n)
{
    if (left <= right)
    {
        int mid = (left + right) / 2;
 
        // base condition is, if we are reaching at left
        // corner or right corner of primes[] array then
        // return that corner element because before or
        // after that we don't have any prime number in
        // primes array
        if (mid == 0 || mid == primes.Count - 1)
            return (int)primes[mid];
 
        // now if n is itself a prime so it will be
        // present in primes array and here we have
        // to find nearest prime less than n so we
        // will return primes[mid-1]
        if ((int)primes[mid] == n)
            return (int)primes[mid - 1];
 
        // now if primes[mid]<n and primes[mid+1]>n
        // that mean we reached at nearest prime
        if ((int)primes[mid] < n &&
            (int)primes[mid + 1] > n)
            return (int)primes[mid];
        if (n < (int)primes[mid])
            return binarySearch(left, mid - 1, n);
        else
            return binarySearch(mid + 1, right, n);
    }
    return 0;
}
 
// Driver code
static void Main()
{
    Sieve();
    int n = 17;
    Console.WriteLine(binarySearch(0,
                      primes.Count - 1, n));
}
}
 
// This code is contributed by chandan_jnu

<?php
// PHP program to find the nearest
// prime to n.
 
$MAX = 10000;
 
// array to store all primes less
// than 10^6
$primes = array();
 
// Utility function of Sieve of Sundaram
function Sieve()
{
    global $MAX, $primes;
    $n = $MAX;
 
    // In general Sieve of Sundaram, produces
    // primes smaller than (2*x + 2) for a
    // number given number x
    $nNew = (int)(sqrt($n));
 
    // This array is used to separate numbers
    // of the form i+j+2ij from others where
    // 1 <= i <= j
    $marked = array_fill(0, (int)($n / 2 + 500), 0);
 
    // eliminate indexes which does not
    // produce primes
    for ($i = 1; $i <= ($nNew - 1) / 2; $i++)
        for ($j = ($i * ($i + 1)) << 1;
             $j <= $n / 2; $j = $j + 2 * $i + 1)
            $marked[$j] = 1;
 
    // Since 2 is a prime number
    array_push($primes, 2);
 
    // Remaining primes are of the form
    // 2*i + 1 such that marked[i] is false.
    for ($i = 1; $i <= $n / 2; $i++)
        if ($marked[$i] == 0)
            array_push($primes, 2 * $i + 1);
}
 
// modified binary search to find nearest
// prime less than N
function binarySearch($left, $right, $n)
{
    global $primes;
    if ($left <= $right)
    {
        $mid = (int)(($left + $right) / 2);
 
        // base condition is, if we are reaching
        // at left corner or right corner of
        // primes[] array then return that corner
        // element because before or after that
        // we don't have any prime number in
        // primes array
        if ($mid == 0 || $mid == count($primes) - 1)
            return $primes[$mid];
 
        // now if n is itself a prime so it will
        // be present in primes array and here
        // we have to find nearest prime less than
        // n so we will return primes[mid-1]
        if ($primes[$mid] == $n)
            return $primes[$mid - 1];
 
        // now if primes[mid]<n and primes[mid+1]>n
        // that means we reached at nearest prime
        if ($primes[$mid] < $n && $primes[$mid + 1] > $n)
            return $primes[$mid];
        if ($n < $primes[$mid])
            return binarySearch($left, $mid - 1, $n);
        else
            return binarySearch($mid + 1, $right, $n);
    }
    return 0;
}
 
// Driver Code
Sieve();
$n = 17;
echo binarySearch(0, count($primes) - 1, $n);
     
// This code is contributed by chandan_jnu
?>

<script>
 
       // JavaScript program to find the nearest prime to n.
       // array to store all primes less than 10^6
       var primes = [];
 
       // Utility function of Sieve of Sundaram
       var MAX = 1000000;
       function Sieve()
       {
           let n = MAX;
 
           // In general Sieve of Sundaram, produces primes
           // smaller than (2*x + 2) for a number given
           // number x
           let nNew = parseInt(Math.sqrt(n));
 
           // This array is used to separate numbers of the
           // form i+j+2ij from others where  1 <= i <= j
           var marked = new Array(n / 2 + 500).fill(0);
 
           // eliminate indexes which does not produce primes
           for (let i = 1; i <= parseInt((nNew - 1) / 2); i++)
               for (let j = (i * (i + 1)) << 1; j <= parseInt(n / 2); j = j + 2 * i + 1)
                   marked[j] = 1;
 
           // Since 2 is a prime number
           primes.push(2);
 
           // Remaining primes are of the form 2*i + 1 such
           // that marked[i] is false.
           for (let i = 1; i <= parseInt(n / 2); i++)
               if (marked[i] == 0)
                   primes.push(2 * i + 1);
       }
 
       // modified binary search to find nearest prime less than N
       function binarySearch(left, right, n) {
           if (left <= right) {
               let mid = parseInt((left + right) / 2);
 
               // base condition is, if we are reaching at left
               // corner or right corner of primes[] array then
               // return that corner element because before or
               // after that we don't have any prime number in
               // primes array
               if (mid == 0 || mid == primes.length - 1)
                   return primes[mid];
 
               // now if n is itself a prime so it will be present
               // in primes array and here we have to find nearest
               // prime less than n so we will return primes[mid-1]
               if (primes[mid] == n)
                   return primes[mid - 1];
 
               // now if primes[mid]<n and primes[mid+1]>n that
               // mean we reached at nearest prime
               if (primes[mid] < n && primes[mid + 1] > n)
                   return primes[mid];
               if (n < primes[mid])
                   return binarySearch(left, mid - 1, n);
               else
                   return binarySearch(mid + 1, right, n);
           }
           return 0;
       }
 
       // Driver program to run the case
       Sieve();
       let n = 17;
       document.write(binarySearch(0, primes.length - 1, n));
 
       // This code is contributed by Potta Lokesh
   </script>

13

Si tiene otro enfoque para resolver este problema, compártalo en los comentarios.
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a contribuir@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.