Project Euler 35

题目

Circular primes

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?

解决方法

除了$2$和$5$，容易知道，如果素数只要包含了数位$024568$，那么这些素数都不符合条件。因为经过循环移位后，这些数一定会变成$2$的倍数或者是$5$的倍数。

因此，仅需将剩下的这些数一个个进行枚举判断。

循环位移通过字符串直接进行操作。

代码

from tools import get_prime

N = 10 ** 6
pr = set(x for x in get_prime(N) if all(c not in str(x) for c in "024568"))


def change(x: int):
    s = str(x)
    return int(s[-1] + s[:-1])


ans = int(N >= 2) + int(N >= 3)
for x in pr:
    m = len(str(x))
    ok = 1
    for i in range(m):
        if x not in pr:
            ok = 0
            break
        x = change(x)
    ans += ok
print(ans)