64 lines
1.5 KiB
Python
64 lines
1.5 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# 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?
|
|
|
|
from projecteuler import sieve, timing
|
|
|
|
|
|
# Calculate all primes below one million, then check if they're circular.
|
|
N = 1000000
|
|
primes = sieve(N)
|
|
|
|
|
|
def is_circular_prime(n: int) -> bool:
|
|
# If n is not prime, it's obviously not a circular prime.
|
|
if primes[n] == 0:
|
|
return False
|
|
|
|
# The primes below 10 are circular primes.
|
|
if primes[n] == 1 and n < 10:
|
|
return True
|
|
|
|
tmp = n
|
|
count = 0
|
|
|
|
# If the number has one or more even digits, it can't be a circular prime.
|
|
# because at least one of the rotations will be even.
|
|
while tmp > 0:
|
|
if tmp % 2 == 0:
|
|
return False
|
|
|
|
# Count the number of digits.
|
|
count = count + 1
|
|
tmp = tmp // 10
|
|
|
|
for _ in range(1, count):
|
|
# Generate rotations and check if they're prime.
|
|
n = n % (10 ** (count - 1)) * 10 + n // (10 ** (count - 1))
|
|
|
|
if primes[n] == 0:
|
|
return False
|
|
|
|
return True
|
|
|
|
|
|
@timing
|
|
def p035() -> None:
|
|
count = 13
|
|
|
|
# Calculate all primes below one million, then check if they're circular.
|
|
for i in range(101, N, 2):
|
|
if is_circular_prime(i):
|
|
count = count + 1
|
|
|
|
print('Project Euler, Problem 35')
|
|
print(f'Answer: {count}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p035()
|