sol1.py

"""
The number,197, is called a circular prime because all rotations of the digits:
197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2,3, 5, 7, 11, 13, 17, 31, 37, 71,73,
79, and 97.

How many circular primes are there below one million?
"""

"""
To solve this problem in an efficient manner, we will first mark all the primes
below 1 million using the Seive of Eratosthenes.

Then, out of all the primes, we will rule out the numbers which contain an even
digit.

After this we will generate each circular combination of the number and check
if all are prime.
"""

seive = [True] * 1000001
i = 2
while i * i <= 1000000:
    if seive[i]:
        for j in range(i * i, 1000001, i):
            seive[j] = False
    i += 1


def is_prime(n: int) -> bool:
    """
    Returns True if n is prime,
    False otherwise, for 2<=n<=1000000
    >>> is_prime(87)
    False
    >>> is_prime(23)
    True
    >>> is_prime(25363)
    False
    """
    return seive[n]


def even_digit(n: int) -> bool:
    """
    Returns True if n contains an even digit
    otherwise False
    >>> even_digit(0)
    True
    >>> even_digit(975317933)
    False
    >>> even_digit(-245679)
    True
    """
    digits = "02468"
    for i in digits:
        if i in str(n):
            return True
    return False


def compute() -> int:
    """
    Returns the total count of all numbers
    below 1 million, which are circular primes
    >>> compute()
    55
    """
    limit = 1000000
    count = 1  # count already includes the number 2.
    for num in range(3, limit + 1, 2):
        if is_prime(num) and not even_digit(num):
            str_num = str(num)
            list_nums = [int(str_num[j:] + str_num[:j]) for j in range(len(str_num))]
            if all(list(map(is_prime, list_nums))):
                count += 1
    return count


if __name__ == "__main__":
    print(compute())