时间戳

首页 > 解决方案 > 需要帮助解决 Project Euler 问题 #35 python？

python - 需要帮助解决 Project Euler 问题 #35 python？

问题描述

我在 Project Euler 上遇到过这个问题，问题是

数字 197 被称为圆素数，因为数字的所有旋转：197、971 和 719 本身都是素数。

100 以下的素数有 13 个：2、3、5、7、11、13、17、31、37、71、73、79 和 97。

一百万以下有多少个圆素数？

经过许多变化后，我的代码如下所示：

def circularPrimes(n):
  primeList, sieve, circularPrime = [], [True] * n, True
  for p in range(2,n):
    if sieve[p]:
      pi = str(p)
      for i in range(0,len(pi)):
        rotatedNumber = pi[i:len(pi)] + pi[0:i]
        rotatedNumber1 = int(rotatedNumber)
        if not sieve[rotatedNumber1]:
          circularPrime = False
      if circularPrime:
        primeList.append(p)
      for i in range(p*p,n,p):
        sieve[i] = False
  return len(primeList)
print(circularPrimes(1000000))

为什么它不起作用，为什么不管我放什么它都会返回 7？所有批评都表示赞赏

标签： python

解决方案

您永远不会重置circularPrime为True，因此一旦设置为False，它将保留False在您测试的所有未来数字中。此外，您在完成筛子之前检查当前数字的旋转，但是您还不知道这些旋转（可能大于原始数字）是否真的是素数。如果将筛子创建和旋转检查分开，它应该可以工作：

def circularPrimes(n):
    primeList, sieve = [], [True] * n
    for p in range(2,n):
        if sieve[p]:
            for i in range(p*p,n,p):
                sieve[i] = False
    for p in range(2,n):
        if sieve[p]:
            circularPrime = True
            pi = str(p)
            for i in range(0,len(pi)):
                rotatedNumber = pi[i:len(pi)] + pi[0:i]
                rotatedNumber1 = int(rotatedNumber)
                if not sieve[rotatedNumber1]:
                    circularPrime = False
            if circularPrime:
                primeList.append(p)
    return len(primeList)

（有趣的是，即使您只是circularPrime在每次迭代中重置，它也会给出相同（正确）的结果，但这可能是巧合，或者有我不明白的更深层次的数学原因。）

推荐阅读