项目欧拉＃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）

回答

相关问题