我正在尝试尝试欧拉项目的第 35 个问题 (click here)。问题是这样的:
The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.
There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.
How many circular primes are there below one million?
所以我创建了一个包含前百万个数的筛子，以筛选出所有小于一百万的素数，并用它来比较素数的旋转结果。
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)
这个程序给出了 100 万以下的循环素数的数量是 54，而实际答案是 55。有人能帮我指出我哪里出错了吗？
注意:
- retCircular(n) 是一个用户定义的函数，它返回数组中数字的所有循环形式。
- 'sieve' 是一个 bool 值数组，它在所有主要位置索引处包含 True，在所有复合位置索引处包含 False。
P/S，如果谁有更好的解决方法，请告诉我!
最佳答案
我将在这里使用我的顾问的 ESP:您的 retCircular 方法没有正确处理重复模式，这使得它错过了 repunit(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
关于python - Project Euler #35 - Circular Primes(结果不正确 1)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33577555/