Check a number for Permutable Prime

0 1 11 minutes read

Given a number N, task is to Check whether it is a permutable prime number or not. A Permutable prime number is that number which after switching the position of digits through any permutation is also prime. Some of the permutable prime numbers are 2, 3, 5, 7, 11, etc. Prerequisites : Primality Test | CPP next_permute() Examples :

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

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

Approach : 1) Construct Sieve of Eratosthenes to find the prime numbers efficiently. 2) Either generate every permutation of the number by switching its digits or use inbuilt C++ function next_permutation to check whether it is prime 3) If any permutation of digits is not prime, simply answer is NO, otherwise YES. Below is the implementation of above approach.

C++

// 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;
}

Java

import java.util.Arrays;
 
public class PermutablePrime {
 
    // Define the maximum limit for the sieve of Eratosthenes
    static final int MAX = 1000001;
 
    // Create a boolean array to store the prime numbers
    static boolean[] primes = new boolean[MAX];
 
    // Sieve of Eratosthenes algorithm to find all prime numbers
    static void sieveOfEratosthenes() {
        // Initialize all values in the array to true
        Arrays.fill(primes, true);
 
        // Mark 1 as not prime
        primes[1] = false;
 
        // Loop through all values from 2 to sqrt(MAX) and mark multiples as not prime
        for (int i = 2; i * i < MAX; i++) {
            if (primes[i]) {
                for (int j = i * 2; j < MAX; j += i) {
                    primes[j] = false;
                }
            }
        }
    }
 
    // Function to check if a number is permutable prime
    static boolean checkPermutablePrime(int N) {
        // Reset the primes array and run the sieve of Eratosthenes algorithm
        Arrays.fill(primes, true);
        sieveOfEratosthenes();
 
        // Create an array to store the digits of the number
        int[] num = new int[7];
        int pos = 0;
        while (N > 0) {
            num[pos++] = N % 10;
            N /= 10;
        }
        int SZ = pos;
 
        // Flag to check if any permutation of the number is not prime
        int flag = 0;
 
        // Sort the digits of the number in ascending order and generate all permutations
        Arrays.sort(num, 0, SZ);
        do {
            // Convert the current permutation to a number and check if it is not prime
            int temp = 0;
            pos = 0;
            while (pos < SZ) {
                temp = temp * 10 + num[pos];
                pos++;
            }
            if (!primes[temp]) {
                flag = 1;
                break;
            }
        } while (nextPermutation(num, SZ));
 
        // If any permutation is not prime, return false
        if (flag == 1) {
            return false;
        }
 
        // Otherwise, return true
        return true;
    }
 
    // Function to generate the next permutation of an array of integers
    static boolean nextPermutation(int[] num, int SZ) {
        int i = SZ - 2;
 
        // Find the index of the first element from the right that is smaller than its next element
        while (i >= 0 && num[i] >= num[i + 1]) {
            i--;
        }
 
        // If no such element is found, the array is already in descending order and has no next permutation
        if (i == -1) {
            return false;
        }
 
        // Find the index of the smallest element from the right that is greater than the above element
        int j = SZ - 1;
        while (num[j] <= num[i]) {
            j--;
        }
 
        // Swap the above two elements
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
 
        // Reverse the order of the remaining elements to generate the next lexicographically larger permutation
        int left = i + 1, right = SZ - 1;
        while (left < right) {
            temp = num[left];
            num[left++] = num[right];
            num[right--] = temp;
        }
        return true;
    }
 
// driver code 
    public static void main(String[] args)
    {
        int N = 31;
        System.out.println(checkPermutablePrime(N) ? "Yes" : "No");
        N = 19;
        System.out.println(checkPermutablePrime(N) ? "Yes" : "No");
    }
} // this code contributed by devendra 
           

Python3

# Python3 Program to check whether number is
# permutable prime or not
import itertools
MAX = 1000001
 
# Sieve of Eratosthenes to find the
# prime numbers upto MAX efficiently
def sieveOfEratosthenes(primes):
     
    # 1 is neither prime nor composite
    primes[1] = False;
 
    for i in range(2, int(MAX ** 0.5) + 1): 
 
        # If prime[i] is not changed,
        # then it is a prime
        if (primes[i] == True): 
 
            # Update all multiples of i
            for j in range(i + i, MAX, i):
                primes[j] = False;
     
    return primes
 
# Function returns 1 if the number N is
# permutable prime otherwise not
def checkPermutablePrime(N):
 
    # Boolean Array for prime numbers
    primes = [True for _ in range(MAX)]
     
    primes = sieveOfEratosthenes(primes);
 
    # Creating Array to store digits
    num = list(map(int, str(N)))
     
     
    # Creating all permutations of the list
    permutations = list(itertools.permutations(num));
 
    ind = 0
     
    flag = 0
    for num in permutations:
 
        # Construct the number again
        # from array of digits
        temp = int("".join(list(map(str, num))))
 
        # check if it is prime of not
        if (primes[temp] == False): 
            flag = 1;
            break;
     
    # If flag is 1, number
    # is not permutable prime
    return not flag
 
# Driver Code to check above functions
N = 31;
print(["No", "Yes"][checkPermutablePrime(N) == 1])
 
N = 19;
print(["No", "Yes"][checkPermutablePrime(N) == 1])
 
# This code is contributed by phasing17

C#

using System;
 
class PermutablePrime {
    // Define the maximum limit for the sieve of
    // Eratosthenes
    static readonly int MAX = 1000001;
 
    // Create a boolean array to store the prime numbers
    static bool[] primes = new bool[MAX];
 
    // Sieve of Eratosthenes algorithm to find all prime
    // numbers
    static void SieveOfEratosthenes()
    {
        // Initialize all values in the array to true
        Array.Fill(primes, true);
 
        // Mark 1 as not prime
        primes[1] = false;
 
        // Loop through all values from 2 to sqrt(MAX) and
        // mark multiples as not prime
        for (int i = 2; i * i < MAX; i++) {
            if (primes[i]) {
                for (int j = i * 2; j < MAX; j += i) {
                    primes[j] = false;
                }
            }
        }
    }
 
    // Function to check if a number is permutable prime
    static bool CheckPermutablePrime(int N)
    {
        // Reset the primes array and run the sieve of
        // Eratosthenes algorithm
        Array.Fill(primes, true);
        SieveOfEratosthenes();
 
        // Create an array to store the digits of the number
        int[] num = new int[7];
        int pos = 0;
        while (N > 0) {
            num[pos++] = N % 10;
            N /= 10;
        }
        int SZ = pos;
 
        // Flag to check if any permutation of the number is
        // not prime
        int flag = 0;
 
        // Sort the digits of the number in ascending order
        // and generate all permutations
        Array.Sort(num, 0, SZ);
        do {
            // Convert the current permutation to a number
            // and check if it is not prime
            int temp = 0;
            pos = 0;
            while (pos < SZ) {
                temp = temp * 10 + num[pos];
                pos++;
            }
            if (!primes[temp]) {
                flag = 1;
                break;
            }
        } while (NextPermutation(num, SZ));
 
        // If any permutation is not prime, return false
        if (flag == 1) {
            return false;
        }
 
        // Otherwise, return true
        return true;
    }
 
    // Function to generate the next permutation of an array
    // of integers
    static bool NextPermutation(int[] num, int SZ)
    {
        int i = SZ - 2;
 
        // Find the index of the first element from the
        // right that is smaller than its next element
        while (i >= 0 && num[i] >= num[i + 1]) {
            i--;
        }
 
        // If no such element is found, the array is already
        // in descending order and has no next permutation
        if (i == -1) {
            return false;
        }
 
        // Find the index of the smallest element from the
        // right that is greater than the above element
        int j = SZ - 1;
        while (num[j] <= num[i]) {
            j--;
        }
 
        // Swap the above two elements
        int temp = num[i];
        num[i] = num[j];
        num[j] = temp;
 
        // Reverse the order of the remaining elements to
        // generate the next lexicographically larger
        // permutation
        int left = i + 1, right = SZ - 1;
        while (left < right) {
            temp = num[left];
            num[left++] = num[right];
            num[right--] = temp;
        }
        return true;
    }
 
    // driver code
    public static void Main(string[] args)
    {
        int N = 31;
        Console.WriteLine(CheckPermutablePrime(N) ? "Yes"
                                                  : "No");
        N = 19;
        Console.WriteLine(CheckPermutablePrime(N) ? "Yes"
                                                  : "No");
    }
}
 
// this code contributed by phasing17

PHP

<?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
?>

Javascript

// JavaScript Program to check whether number is
// permutable prime or not
 
 
let MAX = 1000001
 
 
// Function to calculate and store all
// the next permutations of an array
const permutator = (nums) => {
  let permutations = [];
 
  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      permutations.push(m)
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next))
     }
   }
 }
 
 permute(nums)
 
 return permutations;
}
 
// Sieve of Eratosthenes to find the
// prime numbers upto MAX efficiently
function sieveOfEratosthenes(primes)
{
    // 1 is neither prime nor composite
    primes[1] = false;
 
    for (var 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 (var j = i * 2; j < MAX; j += i)
                primes[j] = false;
        }
    }
}
 
// Function returns 1 if the number N is
// permutable prime otherwise not
function checkPermutablePrime(N)
{
    // Boolean Array for prime numbers
    let primes = new Array(MAX).fill(true);
 
 
    sieveOfEratosthenes(primes);
 
    // Creating Array to store digits
    let num = new Array(7);
 
    // Convert the number into array of digits
    let pos = 0;
    while (N > 0) {
        num[pos++] = N % 10;
        N = Math.floor(N / 10);
    }
 
    // Size of Array
    let SZ = pos;
    let flag = 0;
 
    num.sort();
     
    var ind = 0;
     
    let permutations = permutator(num);
     
    do {
 
        // Construct the number again
        // from array of digits
        let 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;
        }
        num = permutations[ind++];
    } while (ind < permutations.length)
 
    // If flag is 1, number
    // is not permutable prime
    if (flag)
        return false;
 
    return true;
}
 
// Driver Code to check above functions
let N = 31;
console.log((checkPermutablePrime(N) == 1 ? 
                      "Yes" : "No"));
 
N = 19;
console.log((checkPermutablePrime(N) == 1 ? 
                      "Yes" : "No"));
                       
 
 
// This code is contributed by phasing17

Output:

Yes
No

Time Complexity : O(n * log(log(n)) + n!). The sieve of Eratosthenes has a time complexity of O(n * log(log(n))) for finding all primes up to a given number, and the checking for permutations of the digits has a time complexity of O(n!), where n is the number of digits in the input number.

space complexity :O(n), where n is the number of integers up to MAX. This is because the program uses an array of size MAX to store the prime numbers found by the Sieve of Eratosthenes.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!