Siguiente palíndromo primo más pequeño

Dado un entero positivo N donde $1 \leq N \leq 10^{9}$ . La tarea es encontrar el palíndromo primo más pequeño mayor o igual a N.
Ejemplos:

Input: 8
Output: 11

Input: 7000000000
Output: 10000500001

Acercarse:

El enfoque de Naive es hacer un bucle desde N + 1 hasta que encontremos el siguiente palíndromo primo más pequeño mayor o igual que N .
Enfoque eficiente:
digamos que P = R es el siguiente palíndromo primo más pequeño mayor o igual que N .
Ahora, dado que R es un palíndromo, la primera mitad de los dígitos de R se puede usar para determinar R hasta dos posibilidades. Sea k la primera mitad de los dígitos en R . Por ej. si k = 123 , entonces R = 12321 o R = 123321.
Por lo tanto, iteramos a través de cada k hasta 10 ⁵ y creamos el palíndromo asociado R , y comprobamos si R es primo o no.
Además, manejaremos los palíndromos pares e impares por separado, y los dividiremos cuando encontremos nuestro resultado.
A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
 
// Function to check whether
// a number is prime
bool isPrime(ll n)
{
    if (n < 2) return false;
     
    for (ll i = 2; i <= sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
 
// function to generate next
// smallest prime palindrome
ll nextPrimePalindrome(ll N)
{
for (ll k = 1; k < 1000000; k++)
{
     
    // Check for odd-length palindromes
    string s = to_string(k);
    string z(s.begin(), s.end());
    reverse(z.begin(), z.end());
 
    // eg. s = '1234' to x = int('1234321')
    ll x = stoll(s + z.substr(1));
 
    if (x >= N and isPrime(x)) return x;
 
    // Check for even-length palindromes
    s = to_string(k);
    z = string(s.begin(), s.end());
    reverse(z.begin(), z.end());
 
    // eg. s = '1234' to x = int('12344321')
    x = stoll(s + z);
 
    if (x >= N and isPrime(x)) return x;
}
}
 
// Driver Code
int main()
{
    ll N = 7000000000;
     
    // Function call to print answer
    cout << nextPrimePalindrome(N) << endl;
     
    return 0;
}
 
// This code is contributed by
// sanjeev2552

Java

// Java implementation of above approach
class GFG
{
 
// Function to check whether
// a number is prime
static boolean isPrime(long n)
{
    if (n < 2) return false;
     
    for (long i = 2; i <= Math.sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
 
// reverse the String
static String reverse(String s)
{
    String s1 = "";
    for(int i = s.length() - 1; i >= 0; i--)
        s1 += s.charAt(i);
     
    return s1;
}
 
// function to generate next
// smalongest prime palindrome
static long nextPrimePalindrome(long N)
{
    for (long k = 1; k < 1000000l; k++)
    {
         
        // Check for odd-length palindromes
        String s = ""+k;
        String z;
        z = reverse(s);
     
        // eg. s = '1234' to x = int('1234321')
        long x = Long.parseLong(s + z.substring(1, z.length()));
     
        if (x >= N && isPrime(x))
            return x;
     
        // Check for even-length palindromes
        s = ""+(k);
        z = s;
        z = reverse(z);
     
        // eg. s = '1234' to x = int('12344321')
        x = Long.parseLong(s + z);
     
        if (x >= N && isPrime(x)) return x;
    }
    return -1;
}
 
// Driver Code
public static void main(String args[])
{
    long N = 7000000000l;
     
    // Function calong to print answer
    System.out.println( nextPrimePalindrome(N) );
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation of above approach
import math
 
# Function to check whether a number is prime
def is_prime(n):
    return n > 1 and all(n % d for d in range(2, int(math.sqrt(n)) + 1))
 
# function to generate next smallest prime palindrome
def NextprimePalindrome(N):
 
    for k in range(1, 10**6):
 
        # Check for odd-length palindromes
        s = str(k)
        x = int(s + s[-2::-1])  # eg. s = '1234' to x = int('1234321')
 
        if x >= N and is_prime(x):
            return x
 
        # Check for even-length palindromes
        s = str(k)
        x = int(s + s[-1::-1])  # eg. s = '1234' to x = int('12344321')
 
        if x >= N and is_prime(x):
            return x
 
# Driver code
N = 7000000000
 
# Function call to print answer
print(NextprimePalindrome(N))
 
# This code is written by
# Sanjit_Prasad

C#

// C# implementation of above approach
using System;
 
class GFG
{
 
// Function to check whether
// a number is prime
static bool isPrime(long n)
{
    if (n < 2) return false;
     
    for (long i = 2; i <= Math.Sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
 
// reverse the String
static String reverse(String s)
{
    String s1 = "";
    for(int i = s.Length - 1; i >= 0; i--)
        s1 += s[i];
     
    return s1;
}
 
// function to generate next
// smalongest prime palindrome
static long nextPrimePalindrome(long N)
{
    for (long k = 1; k < 1000000; k++)
    {
         
        // Check for odd-length palindromes
        String s = ""+k;
        String z;
        z = reverse(s);
     
        // eg. s = '1234' to x = int('1234321')
        long x = long.Parse(s + z.Substring(1, z.Length - 1));
     
        if (x >= N && isPrime(x))
            return x;
     
        // Check for even-length palindromes
        s = ""+(k);
        z = s;
        z = reverse(z);
     
        // eg. s = '1234' to x = int('12344321')
        x = long.Parse(s + z);
     
        if (x >= N && isPrime(x)) return x;
    }
    return -1;
}
 
// Driver Code
public static void Main(String []args)
{
    long N = 7000000000;
     
    // Function calong to print answer
    Console.WriteLine( nextPrimePalindrome(N) );
}
}
 
// This code is contributed by PrinciRaj1992

Javascript

<script>
 
// Javascript  implementation of above approach
 
// Function to check whether
// a number is prime
function isPrime( n)
{
    if (n < 2) return false;
     
    for (var i = 2; i <= Math.sqrt(n); i++)
    {
        if (n % i == 0) return false;
    }
    return true;
}
 
// function to generate next
// smallest prime palindrome
 
function reverse( s)
{
    var s1 = "";
    for(var i = s.length - 1; i >= 0; i--)
        s1 += s[i];
     
    return s1;
}
 
function nextPrimePalindrome( N)
{
for (var k = 1; k < 1000000; k++)
{
     
    // Check for odd-length palindromes
    var s = ""+k;
    var z;
    z=reverse(s);
 
    // eg. s = '1234' to x = int('1234321')
    var x = Number(s + z.substring(1,z.length));
 
    if (x >= N && isPrime(x)) return x;
 
    // Check for even-length palindromes
    s =  ""+k;
    z = s;
     z=reverse(z);
 
    // eg. s = '1234' to x = int('12344321')
    x = Number(s + z);
 
    if (x >= N && isPrime(x)) return x;
}
}
 
var N = 7000000000;
// Function call to find maximum value
document.write(nextPrimePalindrome(N) + "<br>");
 
// This code is contributed by SoumikMondal
 
</script>

Producción:

10000500001

Complejidad de tiempo: O(N*sqrt(N)) donde N es el límite superior y el término sqrt(N) proviene de verificar si un candidato es primo.

Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Java

Python3

C#

Javascript

Deja una respuesta Cancelar la respuesta