項目歐拉＃35 - 通函（不正確的結果1）

我試圖嘗試項目歐勒（click here）的第35個問題。問題如下所示：項目歐拉＃35 - 通函（不正確的結果1）

數字197被稱爲圓形素數，因爲數字的所有旋轉：197,971和719本身都是素數。
在100以下有13個這樣的素數：2,3,5,7,11,13,17,31,37,71,73,79和97.
在100萬以下有多少個圓形素數？

因此，我創建了一個第一百萬個數的篩子，以獲得一百萬以下的所有素數，並用它來比較素數的旋轉結果。

arr = [] 

for i in range(2, len(sieve)): 
    if sieve[i]: 
     sub_arr = retCircular(i) 
     count = len(sub_arr) 
     carry = 0 
     for j in sub_arr: 
      if sieve[j]: 
       carry += 1 
       sieve[j] = False 
      else: 
       break 
     if carry == count: 
      for j in sub_arr: 
       arr.append(j) 

print "Number of circular primes =", len(arr)

這個節目給了圓形的素數的數量在1萬至54被，而實際的答案是55，可能有人幫助我，我哪裏錯了？

注：

retCircular（n）是一個用戶定義的功能，它返回號碼的所有圓形形式的陣列。
'sieve'是一個布爾值數組，其中包含所有主要位置索引處的True和所有合成位置索引處的False。

P/S，如果有人有更好的方法來解決問題，請讓我知道！

來源

2015-11-07 Ishaan Saxena

歡迎StackOverflow上。請閱讀並遵守幫助文檔中的發佈準則。 [最小，完整，可驗證的示例]（http://stackoverflow.com/help/mcve）適用於此處。在您發佈代碼並準確描述問題之前，我們無法有效幫助您。特別是，我們需要代碼來重現問題。我們也可以使用你的邏輯和數據 - 你缺少什麼素數？ – Prune

在循環之前添加它：'print sieve [2]'。如果答案是「3」，則跳過第一個素數。 –

考慮如果您的初始素數（在測試循環性之前）包含數字0,2,4,5,6,8中的任何一個將會發生什麼。小心使用單數字素數2和5。 – rossum

我要在這裏用我的顧問ESP：你retCircular方法不正確處理重複模式，這使得它錯過循環單位素數（1的字符串）。特別是，retCircular（11）返回[11,11]，這會使您的算法錯過該數字作爲圓形素數。這裏是我的方法的蠻力版本：

def retCircular(prime): 
    prime_str = str(prime) 
    family = [prime] 
    for _ in range(len(prime_str)-1): 
     prime_str = prime_str[1:] + prime_str[0] 
     child = int(prime_str) 
     if child == prime: 
      break 
     family.append(int(prime_str)) 
    return family

...我得到55米的素數與主程序：

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

來源

2015-11-07 00:42:17 Prune

項目歐拉＃35 - 通函（不正確的結果1）

回答

相關問題