Encuentra el siguiente primo palíndromo

Encuentre el número palíndromo más pequeño que también sea primo y mayor que el número N dado.
Ejemplos: 
 

Input : N = 7
Output :11
11 is the smallest palindrome prime which
is greater than N.

Input : N = 112
Output : 131

Un enfoque simple es iniciar un bucle desde N+1. Para cada número, comprueba si es palíndromo y primo .
Una solución eficiente se basa en las siguientes observaciones. Todo palíndromo con dígitos pares es múltiplo de 11. 
Podemos probar de la siguiente manera: 
11 % 11 = 0 
1111 % 11 = 0 
111111 % 11 = 0 
11111111 % 11 = 0
Entonces: 
1001 % 11 = (1111 – 11 * 10) % 11 = 0 
100001 % 11 = (111111 – 1111 * 10) % 11 = 0 
10000001 % 11 = (11111111 – 111111 * 10) % 11 = 0
Para cualquier palíndromo con dígitos pares: 
abcddcba % 11 
= (a * 10000001 + b * 100001 * 10 + c * 1001 * 100 + d * 11 * 1000) % 11 
= 0
Todo palíndromo con dígitos pares es múltiplo de 11. 
Entonces, entre ellos, 11 es el único primo 
si (8 <= N <= 11) devuelve 11. 
Para otros, consideramos solo palíndromos con dígitos impares.
 

C++

// CPP program to find next palindromic
// prime for a given number.
#include <iostream>
#include <string>
using namespace std;
 
bool isPrime(int num)
{
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}
 
int primePalindrome(int N)
{
    // if(8<=N<=11) return 11
    if (8 <= N && N <= 11)
        return 11;
 
    // generate odd length palindrome number
    // which will cover given constraint.
    for (int x = 1; x < 100000; ++x) {
     
        string s = to_string(x), r(s.rbegin(), s.rend());
        int y = stoi(s + r.substr(1));
     
        // if y>=N and it is a prime number
        // then return it.
        if (y >= N && isPrime(y))
            return y;
    }
 
    return -1;
}
 
// Driver code
int main()
{
    cout << primePalindrome(112);
    return 0;
}

Java

// Java program to find next palindromic
// prime for a given number.
import java.lang.*;
class Geeks {
 
static boolean isPrime(int num)
{
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}
 
static int primePalindrome(int N)
{
    // if(8<=N<=11) return 11
    if (8 <= N && N <= 11)
        return 11;
 
    // generate odd length palindrome number
    // which will cover given constraint.
    for (int x = 1; x < 100000; ++x) {
     
        String s = Integer.toString(x);
        StringBuffer buffer = new StringBuffer(s);
        buffer.reverse();
         
        int y = Integer.parseInt(s +
        buffer.substring(1).toString());
     
        // if y>=N and it is a prime number
        // then return it.
        if (y >= N && isPrime(y) == true)
            return y;
    }
 
    return -1;
}
 
// Driver code
public static void main(String args[])
{
    System.out.print(primePalindrome(112));
 
}
}

Python3

# Python3 program to find next palindromic
# prime for a given number.
import math as mt
 
def isPrime(num):
 
    if (num < 2 or num % 2 == 0):
        return num == 2
    for i in range(3, mt.ceil(mt.sqrt(num + 1))):
        if (num % i == 0):
            return False
    return True
 
def primePalindrome(N):
 
    # if(8<=N<=11) return 11
    if (8 <= N and N <= 11):
        return 11
 
    # generate odd length palindrome number
    # which will cover given constraint.
    for x in range(1, 100000):
     
        s = str(x)
        d = s[::-1]
        y = int(s + d[1:])
     
        # if y>=N and it is a prime number
        # then return it.
        if (y >= N and isPrime(y)):
            return y
     
# Driver code
print(primePalindrome(112))
 
# This code is contributed by
# Mohit kumar 29

C#

// C# program to find next palindromic
// prime for a given number.
using System;
using System.Text;
using System.Collections;
 
class Geeks {
 
static bool isPrime(int num)
{
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}
 
static int primePalindrome(int N)
{
    // if(8<=N<=11) return 11
    if (8 <= N && N <= 11)
        return 11;
 
    // generate odd length palindrome number
    // which will cover given constraint.
    for (int x = 1; x < 100000; ++x) {
     
        string s = x.ToString();
        char[] buffer = s.ToCharArray();
        Array.Reverse(buffer);
         
        int y = Int32.Parse(s + new string(buffer).Substring(1));
     
        // if y>=N and it is a prime number
        // then return it.
        if (y >= N && isPrime(y) == true)
            return y;
    }
 
    return -1;
}
 
// Driver code
public static void Main()
{
    Console.WriteLine(primePalindrome(112));
}
}
 
// This code is contributed by Mithun Kumar.

PHP

<?php
// PHP program to find next palindromic
// prime for a given number.
 
function isPrime($num)
{
    if ($num < 2 || $num % 2 == 0)
        return $num == 2;
    for ($i = 3; $i * $i <= $num; $i += 2)
        if ($num % $i == 0)
            return false;
    return true;
}
 
function primePalindrome($N)
{
    // if(8<=N<=11) return 11
    if (8 <= $N && $N <= 11)
        return 11;
 
    // generate odd length palindrome number
    // which will cover given constraint.
    for ($x = 1; $x < 100000; ++$x)
    {
        $s = strval($x);
        $r = strrev($s);
        $y = intval($s.substr($r, 1));
     
        // if y>=N and it is a prime number
        // then return it.
        if ($y >= $N && isPrime($y) == true)
            return $y;
    }
 
    return -1;
}
 
// Driver code
print(primePalindrome(112));
 
// This code is contributed by mits
?>

Javascript

<script>
// Javascript program to find next palindromic
// prime for a given number.
 
function isPrime(num)
{
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}
 
function primePalindrome(N)
{
    // if(8<=N<=11) return 11
    if (8 <= N && N <= 11)
        return 11;
 
    // generate odd length palindrome number
    // which will cover given constraint.
    for (let x = 1; x < 100000; ++x)
    {
        let s = String(x);
        let r = s.split("").reverse().join("");
        let y = parseInt(s + r.substr(1));
     
        // if y>=N and it is a prime number
        // then return it.
        if (y >= N && isPrime(y) == true)
            return y;
    }
 
    return -1;
}
 
// Driver code
document.write(primePalindrome(112));
 
// This code is contributed by gfgking
</script>
Producción: 

131

 

Publicación traducida automáticamente

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *