Python 代码优化

Question

最近我发现了一个难题，要求我列出一个数字下的所有循环素数。在这种情况下，循环意味着如果我们旋转数字，它仍然是素数：例如。1193是素数1931年是黄金时期9311 是素数3119是素数

这是我原文编写的代码：

a=[]
upto=1000000
for x in range(upto):
    a.append([x,0])
print('generated table')
a[1][1]=1
a[0][1]=1
for n in range(2,int(math.sqrt(upto))):
    for k in range(2,(int(upto/n)+2)):
        try:
            a[n*k][1]=1
        except IndexError:
            pass
print('sive complete')
p=[]
for e in a:
    if (e[1]==0):
        p.append(e[0])
print('primes generated')
s=[]
for e in p:
    pr=True
    w=str(e)
    if all(c not in w for c in ['2','4','6','8','5','0']):
        for x in (w[i:]+w[:i] for i in range(len(w))):
            if int(x) not in p:
                pr=False
        if pr==True:
            s.append(e)
            print('found',e)
print(s)

它相当慢！（约12秒）我知道，黄金一代并不完美，但最后一点是最慢的。我知道 ups=10e6 的这个过程可以在一秒钟内完成，所以经过一些研究，我删除了任何字符串操作以支持这个函数：

def rotate(n):
    prev=[]
    for l in range(6,0,-1):
        if(n<10**l):
            length=l
    while(n not in prev):
        prev.append(n)
        n=(n // 10) + (n % 10) * 10**(length-1)
        yield n

我还删除了 5,0,2,4,6,8 测试，因为我不知道如何实现它。结果呢？它运行得更慢！（超过十分钟，我想5,0,2,4,6,8测试是个好主意）

我尝试使用 time.time（），但我没有发现任何非常低效的东西（在第一个代码中）。如何改进此代码？我目前正在使用任何不良做法吗？

Answer 1

下面是一些优化的代码：

import math
upto = 1000000
a = [True] * upto
p = []
for n in xrange(2,upto):
    if a[n]:
        p.append(n)
        for k in xrange(2,(upto+n-1)//n):
            a[k*n] = False
print('primes generated')
s = []
p = set(p)
for e in p:
    pr=True
    w=str(e)
    if all(c not in w for c in ['2','4','6','8','5','0']):
        for x in (w[i:]+w[:i] for i in range(len(w))):
            if int(x) not in p:
                pr=False
                break
        if pr:
            s.append(e)
print(s)

最重要的优化：

1. 简化了筛分代码
2. 将素数列表转换为集合。这使得测试x in p对数而不是线性
3. 在发现非素数旋转时添加了中断语句

添加了更干净（但等效）的代码：

import math
upto=1000000
sieve = [True] * upto
primes = set()
for n in xrange(2,upto):
    if sieve[n]:
        primes.add(n)
        for k in xrange(2,(upto+n-1)//n):
            sieve[k*n] = False
def good(e):
    w = str(e)
    for c in w:
        if c not in '1379':
            return False
    for i in xrange(1,len(w)):
        x = int(w[i:]+w[:i])
        if x not in primes:
            return False
    return True
print filter(good,primes)

Answer 2

您可以通过进行集合比较来减少第一次测试所需的时间，而不是每次都像这样进行完整迭代：

flags = set('246850')
if not set(str(e)).intersection(flags):
    # etc...

这不仅是对数缩放，还可以让您在此步骤中拾取另一个 2 的因子。您甚至可以进一步加快速度，并通过将其转换为生成器来使其更加优雅，然后您可以使用该生成器进行最终检查，如下所示：

flags = set('246850')
primes = set(p)
easy_checks = (str(prime) for prime in primes if not set(str(prime)).intersection(flags))

最后，

您可以重写最后一点以摆脱所有附加和其他内容，这往往非常慢，如下所示：

test = lambda number: any((int(number[i:]+number[:i]) in primes for i in xrange(len(number))))
final = [number for number in easy_checks if test(number)]