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) 

這是很多的速度比無優化，但可以進一步優化。