Problem: Circular Prime Number

*Difficulty: Easy

A prime number is a Circular Prime Number if all of its possible rotations are itself prime numbers. Now given a number N check if it is Circular Prime or Not.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer N.

Output:
For each test case in a new line print 1 if the number is circular prime else 0.

Constraints:
1<=T<=100
1<=N<=104

Example:
Input:
2
197
101

Output:
1
0

Explanation:
For first test case:
197 is a Circular Prime because all rotations of 197 are
197, 719, 971 all of the 3 are prime number’s
hence 197 is a circular prime

For second test case:
101 isn’t a prime number as
rotation of 101 yields 110 which isn’t a prime number
hence 101 isn’t circular prime

Implementation: Python

from math import sqrt
def sieve_eratosthenes(n):
    """
        n: bound 
        return all primes number up to n 
    """
    sieve = [True]*(n+1)
    sieve[0] = sieve[1] = False
    bound = int(sqrt(n)) + 1
    for i in range(2, bound):
        if sieve[i]:
            for j in range(i+i, len(sieve), i):
                sieve[j] = False 
    return sieve


def rotations(n):
    """
        return all rotations of n
    """
    s, res = str(n), []
    for _ in range(len(s)):
        temp, s = s, s[-1] + s[:-1]
        res.append(temp)
    return res


def is_prime(primes, n):
    """
        check if a number is prime 
    """
    return primes[n]


def is_circular_prime(n, primes):
    """
        n: a number (integer)
        primes: sieve eratosthenes to check primality 
    """
    all_rotations = map(int, rotations(n))
    return all([is_prime(primes, int(x)) for x in all_rotations])

if __name__ == '__main__':
    t = input()
    primes = sieve_eratosthenes(10000)
    for _ in range(t):
        n = input()
        print 1 if is_circular_prime(n, primes) else 0
Advertisements