Verifique un número para Permutable Prime

Dado un número N, la tarea es comprobar si es un número primo permutable o no.

Un número primo permutable es aquel número que después de cambiar la posición de los dígitos a través de cualquier permutación también es primo. Algunos de los números primos permutables son 2, 3, 5, 7, 11, etc.

Prerrequisitos: Prueba de Primalidad | CPP siguiente_permutar()

Ejemplos:

Input : 31
Output : Yes
Explanation : 
Both 13 and 31 are prime.

Input : 19
Output : No
Explanation : 
19 is prime but 91 is not

Enfoque:
1) Construya la Criba de Eratóstenes para encontrar los números primos de manera eficiente.
2) Genere todas las permutaciones del número cambiando sus dígitos o use la función incorporada de C++ next_permutation para verificar si es primo
3) Si alguna permutación de dígitos no es primo, simplemente responda NO, de lo contrario SÍ.

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

// CPP Program to check whether number is
// permutable prime or not
#include <bits/stdc++.h>
using namespace std;
  
#define MAX 1000001
  
// Sieve of Eratosthenes to find the
// prime numbers upto MAX efficiently
void sieveOfEratosthenes(bool* primes)
{
    // 1 is neither prime nor composite
    primes[1] = false;
  
    for (int i = 2; i * i < MAX; i++) {
  
        // If prime[i] is not changed,
        // then it is a prime
        if (primes[i] == true) {
  
            // Update all multiples of i
            for (int j = i * 2; j < MAX; j += i)
                primes[j] = false;
        }
    }
}
  
// Function returns 1 if the number N is
// permutable prime otherwise not
bool checkPermutablePrime(int N)
{
    // Boolean Array for prime numbers
    bool primes[MAX];
  
    // Initialize all entries as true.
    // A value in prime[i] will finally
    // be false if i is not a prime,
    // else true.
    memset(primes, true, sizeof(primes));
  
    sieveOfEratosthenes(primes);
  
    // Creating Array to store digits
    int num[7];
  
    // Convert the number into array of digits
    int pos = 0;
    while (N > 0) {
        num[pos++] = N % 10;
        N /= 10;
    }
  
    // Size of Array
    int SZ = pos;
    int flag = 0;
  
    sort(num, num + SZ);
  
    do {
  
        // Construct the number again
        // from array of digits
        int temp = 0;
        pos = 0;
        while (pos < SZ) {
            temp = temp * 10 + num[pos];
            pos++;
        }
  
        // check if it is prime of not
        if (primes[temp] == false) {
            flag = 1;
            break;
        }
    } while (next_permutation(num, num + SZ));
  
    // If flag is 1, number
    // is not permutable prime
    if (flag)
        return false;
  
    return true;
}
  
// Driver Code to check above functions
int main()
{
    int N = 31;
    cout << (checkPermutablePrime(N) == 1 ? 
                      "Yes" : "No") << endl;
  
    N = 19;
    cout << (checkPermutablePrime(N) == 1 ? 
                      "Yes" : "No") << endl;
    return 0;
}

<?php
// PHP Program to check 
// whether number is
// permutable prime or not
$MAX = 100001;
$zz;
$l = 0;
  
// to find all permutation
// of that number
function next_permutation($items, 
                          $perms = array( )) 
{
    global $zz, $l;
    if (empty($items)) 
    { 
        $zz[$l++] = join($perms);
    } 
      
    else 
    {
        for ($i = count($items) - 1; 
             $i >= 0; --$i) 
        {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            next_permutation($newitems, $newperms);
        }
    }
    return $zz;
}
  
// Sieve of Eratosthenes to 
// find the prime numbers 
// upto MAX efficiently
function sieveOfEratosthenes($primes)
{
    global $MAX;
      
    // 1 is neither prime 
    // nor composite
    $primes[1] = false;
  
    for ($i = 2; $i * $i < $MAX; $i++)
    {
  
        // If prime[i] is not changed,
        // then it is a prime
        if ($primes[$i] == true)
        {
  
            // Update all multiples of i
            for ($j = $i * 2; 
                 $j < $MAX; $j += $i)
                $primes[$j] = false;
        }
    }
    return $primes;
}
  
// Function returns 1 if the 
// number N is permutable
// prime otherwise not
function checkPermutablePrime($N)
{
    global $MAX, $zz, $l;
      
    // Boolean Array for
    // prime numbers
  
    // Initialize all entries 
    // as true. A value in 
    // prime[i] will finally
    // be false if i is not a 
    // prime, else true.
    $primes = array_fill(0, $MAX, true);
  
    $primes = sieveOfEratosthenes($primes);
  
    // Creating Array 
    // to store digits
    $num = array();
  
    // Convert the number 
    // into array of digits
    $pos = 0;
    while ($N > 0) 
    {
        $num[$pos++] = $N % 10;
        $N = (int)($N / 10);
    }
  
    // Size of Array
    $flag = 0;
  
    sort($num);
    $num1 = next_permutation($num);
    $i = 0;
    while ($i < count($num1))
    {
  
        // Construct the number again
        // from array of digits
        $temp = 0;
        $pos = 0;
        while ($pos < strlen($num1[$i])) 
        {
            $temp = $temp * 10 + 
                ord($num1[$i][$pos]) - 48;
            $pos++;
        }
  
        // check if it is
        // prime of not
        if ($primes[$temp] == false)
        {
            $flag = 1;
            break;
        }
        $i++;
    }
      
    $zz = array();
    $l = 0;
  
    // If flag is 1, number
    // is not permutable prime
    if ($flag)
        return false;
  
    return true;
}
  
// Driver Code
$N = 31;
echo (checkPermutablePrime($N) == 1 ? 
                              "Yes" : "No") . "\n";
  
$N = 19;
echo (checkPermutablePrime($N) == 1 ? 
                              "Yes" : "No") . "\n";
  
// This Code is contributed
// by mits
?>

Yes
No