Comprobar si un número es primo circular o no

Nos dan un número n. Nuestra tarea es verificar si el número es primo circular o no.
Primo circular : Se dice que un número primo es primo circular si después de cualquier permutación cíclica de los dígitos, sigue siendo primo.
Ejemplos: 

Input :  n = 113 
Output : Yes
All cyclic permutations of 113 (311
and 131) are prime. 

Input : 1193
Output : Yes

La idea es simple, generamos todas las permutaciones de un número dado y verificamos cada permutación para primos. Para generar permutaciones, uno por uno movemos el último dígito a la primera posición.  

// Program to check if a number is circular
// prime or not.
#include <iostream>
#include <cmath>
using namespace std;
 
// Function to check if a number is prime or not.
bool isPrime(int n)
{
    // Corner cases
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 
    // This is checked so that we can skip
    // middle five numbers in below loop
    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
 
    return true;
}
 
// Function to check if the number is circular
// prime or not.
bool checkCircular(int N)
{
    // Count digits.
    int count = 0, temp = N;
    while (temp) {
        count++;
        temp /= 10;
    }
 
    int num = N;
    while (isPrime(num)) {
 
        // Following three lines generate the next
        // circular permutation of a number. We move
        // last digit to first position.
        int rem = num % 10;
        int div = num / 10;
        num = (pow(10, count - 1)) * rem + div;
 
        // If all the permutations are checked and
        // we obtain original number exit from loop.
        if (num == N)
            return true;
    }
 
    return false;
}
 
// Driver Program
int main()
{
    int N = 1193;
    if (checkCircular(N))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

// Java Program to check if a number
// is circular prime or not.
import java.lang.*;
 
class GFG
{
    // Function to check if a number is prime or not.
    static boolean isPrime(int n)
    {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can skip
        // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to check if the number is circular
    // prime or not.
    static boolean checkCircular(int N)
    {
        // Count digits.
        int count = 0, temp = N;
        while (temp>0) {
            count++;
            temp /= 10;
        }
 
        int num = N;
        while (isPrime(num)) {
 
        // Following three lines generate the next
        // circular permutation of a number. We
        // move last digit to first position.
        int rem = num % 10;
        int div = num / 10;
        num = (int)((Math.pow(10, count - 1)) * rem)
                                             + div;
 
        // If all the permutations are checked and
        // we obtain original number exit from loop.
        if (num == N)
            return true;
        }
 
        return false;
    }
 
    // Driver Program
    public static void main (String[] args)
    {
        int N = 1193;
        if (checkCircular(N))
        System.out.println("Yes");
        else
        System.out.println("No");
    }
}
/* This code is contributed by Kriti Shukla */

# Python Program to check if a number
# is circular prime or not.
 
import math
 
# Function to check if a number is prime
# or not.
def isPrime(n) :
 
    # Corner cases
    if (n <= 1) :
        return False
    if (n <= 3) :
        return True
         
    # This is checked so that we can skip
    # middle five numbers in below loop
    if (n % 2 == 0 or n % 3 == 0) :
        return False
 
    i = 5
    while i * i <= n :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
     
    return True
     
# Function to check if the number is
# circular prime or not.
def checkCircular(N) :
     
    #Count digits.
    count = 0
    temp = N
    while (temp > 0) :
        count = count + 1
        temp = temp / 10
         
    num = N;
    while (isPrime(num)) :
         
        # Following three lines generate the
        # next circular permutation of a
        # number. We move last digit to
        # first position.
        rem = num % 10
        div = num / 10
        num = (int)((math.pow(10, count - 1))
                                * rem)+ div
 
        # If all the permutations are checked
        # and we obtain original number exit
        # from loop.
        if (num == N) :
            return True
     
    return False
     
# Driver Program
N = 1193;
if (checkCircular(N)) :
    print "Yes"
else :
    print "No"
     
# This code is contributed by Nikita Tiwari

// C# Program to check if a number
// is circular prime or not.
using System;
 
class GFG {
     
    // Function to check if a
    // number is prime or not.
    static bool isPrime(int n)
    {
         
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we
        // can skip middle five numbers
        // in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    // Function to check if the number
    // is circular prime or not.
    static bool checkCircular(int N)
    {
         
        // Count digits.
        int count = 0, temp = N;
        while (temp > 0)
        {
            count++;
            temp /= 10;
        }
 
        int num = N;
        while (isPrime(num))
        {
 
            // Following three lines generate
            // the next circular permutation
            // of a number. We move last digit
            // to first position.
            int rem = num % 10;
            int div = num / 10;
            num = (int)((Math.Pow(10, count -
                         1)) * rem) + div;
     
            // If all the permutations are
            // checked and we obtain original
            // number exit from loop.
            if (num == N)
                return true;
        }
 
        return false;
    }
 
    // Driver code
    public static void Main ()
    {
        int N = 1193;
        if (checkCircular(N))
        Console.Write("Yes");
        else
        Console.Write("No");
    }
}
 
// This code is contributed by Nitin Mittal.

<?php
// Program to check if
// a number is circular
// prime or not.
 
// Function to check if a
// number is prime or not.
function isPrime($n)
{
    // Corner cases
    if ($n <= 1)
        return false;
    if ($n <= 3)
        return true;
 
    // This is checked so that
    // we can skip middle five
    // numbers in below loop
    if ($n % 2 == 0 ||
        $n % 3 == 0)
        return false;
 
    for ($i = 5;
         $i * $i <= $n; $i = $i + 6)
        if ($n % $i == 0 ||
            $n % ($i + 2) == 0)
            return -1;
 
    return true;
}
 
// Function to check if
// the number is circular
// prime or not.
function checkCircular($N)
{
    // Count digits.
    $count = 0;
    $temp = $N;
    while ($temp)
    {
        $count++;
        $temp =(int)$temp / 10;
    }
 
    $num = $N;
    while (isPrime($num))
    {
 
        // Following three lines generate
        // the next circular permutation
        // of a number. We move last digit
        // to first position.
        $rem = $num % 10;
        $div = (int)$num / 10;
        $num = (pow(10, $count - 1)) *
                        $rem + $div;
 
        // If all the permutations are
        // checked and we obtain original
        // number exit from loop.
        if ($num == $N)
            return true;
    }
 
    return -1;
}
 
// Driver Code
$N = 1193;
if (checkCircular($N))
    echo "Yes" ,"\n";
else
    echo "No" ,"\n";
     
// This code is contributed
// by akt_mit
?>

<script>
 
    // Javascript Program to check if a number
    // is circular prime or not.
     
    // Function to check if a
    // number is prime or not.
    function isPrime(n)
    {
          
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
  
        // This is checked so that we
        // can skip middle five numbers
        // in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
  
        for (let i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
  
        return true;
    }
  
    // Function to check if the number
    // is circular prime or not.
    function checkCircular(N)
    {
          
        // Count digits.
        let count = 0, temp = N;
        while (temp > 0)
        {
            count++;
            temp = parseInt(temp / 10, 10);
        }
  
        let num = N;
        while (isPrime(num))
        {
  
            // Following three lines generate
            // the next circular permutation
            // of a number. We move last digit
            // to first position.
            let rem = num % 10;
            let div = parseInt(num / 10, 10);
            num = ((Math.pow(10, count - 1)) * rem) + div;
      
            // If all the permutations are
            // checked and we obtain original
            // number exit from loop.
            if (num == N)
                return true;
        }
  
        return false;
    }
     
    let N = 1193;
    if (checkCircular(N))
      document.write("Yes");
    else
      document.write("No");
     
</script>

Producción: 

Yes

Complejidad de tiempo: O(N*N ^1/2 )

Espacio auxiliar: O(1)
Optimizaciones: 
Claramente, los números que contienen 0, 2, 4, 5, 6 u 8 nunca pueden ser primos circulares, ya que los números que terminan en estos siempre serán divisibles por 2 o 5. Por lo tanto, una de sus permutaciones no será ser un primo. Mientras contamos dígitos en el primer paso, también podemos verificar si el dígito actual es uno de estos.
Este artículo es una contribución de Vineet Joshi . 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 review-team@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.