035. 圆形素数(circular primes)

数字197是一个圆形素数,这是因为所有它各位数的轮换197,971以及719也都是素数。一百以下总共有十三个这样的素数,包括:2,3,5,7,11,13,17,31,37,71,73,79和97。求一百万以下有多少个这样的圆形素数?

分析:首先我们来看一下如何尽可能的缩小待筛选的素数范围。题目已经给出一百以下的所有素数,所以一百以下的的素数不需要再做筛选,只需要考虑一百至一百万之间的所有素数,共有78473个。其次,除二以外的所有素数均为奇数,所以个位数不能是偶数且不为能为五,因为个位数为五的数字可以被五整除,又由于我们这里所求的圆形素数要求一个素数的所有轮换必须都为素数,任何数位上的数都会轮换到个位数上,这就要求整个数字的数位中不能包括偶数和五,只能包括1、3、7、9四个数字的至少两个。比如对于素数262147,做一次轮换就变成621472是一个偶数,不满足圆形素数的条件。为此,我们可以使用集合推导式,要求素数各个位数构成的集合是集合{1,3,7,9}的一个子集,可以将待筛选的素数从78473个降低到1099个。

为了计算特定素数的所有轮换,我们需要编写一个函数,它将特定的数字转化为对应的字符串,并将字符串的第一位拼接到剩余字符串的末尾,如此循环下去只到遍历所有数位,最后将一个数字的所有轮换存入到集合中并返回。在正式进行筛选时,我们只需要对上述满足条件的1099个素数进行筛选,依次检测素数的所有轮换是否为素数,只要有一个不是素数,则停止检测剩下的轮换,并从素数集合中去掉该素数的所有轮换,以避免之后重复检测。如果一个素数的所有轮换都为素数,则是满足条件的圆形素数并保留在集合中。最后我们计算该集合的元素个数并加上一百以下的十三个数,则为一百万以下的所有圆形素数的个数。

from sympy import sieve,isprime

def rotate_set(num):
    s = str(num)
    res = {num}
    for i in range(len(s)):
        new = s[1:] + s[0]
        res.add(int(new))
        s = new
    return res

def main():
    primes = set(sieve.primerange(100,1e6))
    digitset = {'1','3','7','9'}
    res_set = {i for i in primes if set(str(i))<=digitset}
    for ele in res_set:
        x = rotate_set(ele)
        for i in x:
            if isprime(i) == False:
                res_set = res_set-x
                break
    return len(res_set)+13