Python - Project Euler＃35 - 这种方法有什么问题？

Question

问题项目欧拉的35是为这样：

数，197，被称为圆形素因的数字所有旋转：197，971，和719，它们本身的素数。低于2，3，5，7，11，13，17，31，37，71，73，79，和97。

多少圆形素数是否有：

有低于100 13米这样的素数一百万？

我的，比较简陋，方法是首先产生低于1百万的所有素数，然后筛选出所有包含连数字或数字5（因为总是会有一个非黄金置换）的素数。然后，对于这个简化的素数列表中的每个元素，使用itertools模块中的permutations（）函数返回数字的所有可能排列，然后检查这些排列是否不是质数，如果是，则从元素中移除元素素数列表。

from itertools import permutations 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q]  
     q += 1 

def odd_primes(limit): 
    r = list(gen_primes(limit)) 
    for i in r[:]: 
     for j in str(i): 
      if any(int(j)%2 == 0 or int(j) == 5 for j in str(i)): 
       r.remove(i) 
       break 
    r.extend([2,5]) 
    return r  

def circular_list(): 
    prime_list = odd_primes(1000000) 
    for i in prime_list[:]: 
     perm = [''.join(j) for j in permutations(str(i))] 
     if any(int(j) not in prime_list for j in perm): 
      prime_list.remove(i) 
      break 
    return prime_list 

print len(circular_list) 

输出产生一个值，该值在某些边界上不正确。我一直在努力寻找逻辑或代码（或两者）中的错误。 permutations（）函数是一种可行的方法吗？

我知道有更高效的方法，但如果有人能指出我朝这个方向努力的方向，我将不胜感激。

Answer 1

第一个问题是你需要旋转，而不是排列。 deque可以旋转，所以我们可以替代它。第二个问题是odd_primes()是一个速度优化，在基本代码工作之前不应该添加，所以我们现在就放弃它，并且circular_list()直接调用gen_primes()。当然，发现发生器并不是最优的，因为我们必须回顾素数列表并且只能迭代一次发生器。

所以这里是有希望的工作代码用双端队列和无odd_primes()：

from collections import deque 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q]  
     q += 1 

def circular_list(limit): 
    circular = [] 

    primes = list(gen_primes(limit)) 

    for prime in primes: 
     string = str(prime) 
     digits = deque(string) 

     for rotation in range(1, len(string)): 
      digits.rotate(1) 

      if int("".join(digits)) not in primes: 
       break 
     else: 
      circular.append(prime) 

    return circular 

print(circular_list(1000000)) 

，输出：

[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331] 

如果这是有效的输出，现在回去溜进odd_primes()，看看你可以发挥一些技巧来优化速度。

Answer 2

使用来自cdlane的伟大代码并介绍基于具有至少两位数的圆形素数的速度优化只能由数字1,3,7或9的组合组成，因为具有0,2,4， 6或8的最后一位数字使得整除数除以2，以及具有0或5作为最后一个数字使得整除5（从https://en.wikipedia.org/wiki/Circular_prime）你：

from collections import deque 
import re 
import time 

def gen_primes(limit): 
    D = {} 
    q = 2 
    while q <= limit: 
     if q not in D: 
      yield q 
      D[q * q] = [q] 
     else: 
      for p in D[q]: 
       D.setdefault(p + q, []).append(p) 
      del D[q] 
     q += 1 

def exclude_primes(primes_list): 
    regex = re.compile("[024568]") 
    included_primes_list = [str(prime) for prime in primes_list if prime < 10 or regex.search(str(prime)) is None] 
    return included_primes_list 

def circular_list(limit): 
    circular_count = 0 

    primes = set(exclude_primes(gen_primes(limit))) 

    for prime in primes.copy(): # need copy to process allowing update original primes list 
     digits = deque(prime) 

     rotations = set() 
     for rotation in range(len(digits)): 
      digits.rotate(1) 
      rotations.add("".join(digits)) 
     # check all rotations at once 
     if rotations.issubset(primes): 
      circular_count += len(rotations) 
     # remove all rotations already checked from primes list 
     primes.difference_update(rotations) 

    return circular_count 

start_cpu_time = time.clock() 
print("Number of primes:", circular_list(1000000)) 
end_cpu_time = time.clock() 
print("CPU seconds:", end_cpu_time - start_cpu_time) 

这是很多的速度比无优化，但可以进一步优化。