我的欧拉7代码有什么问题？

Question

为什么这不适用于euler问题：https://projecteuler.net/problem=7

def primeornot(n):
    counter=0
    if n==2:
        return True
    else:
        for number in range(2,n):
            if not n%number:
                counter=1
        if counter ==1:
            return False
        if counter==0:
                return True


primes=[]
m=2
while len(primes)<10002:
     if primeornot(m) is True:
        primes.append(m)
        m=m+1
     else:
        m=m+1
print (primes[10000])

[没有语法错误]我已经编辑过了 对我来说，Primeorn看起来不太好。你知道吗

Answer 1

最大的问题是while循环中的条件。在找到100个素数后，您将中断，但您需要找到第10001个素数。

所以这一行：

while len(primes) < 100:

意味着每当你找到100个素数，你就会退出while循环。如果你需要的话，我会进一步澄清的；只要告诉我就行了。你知道吗

Answer 2

让我们在代码中添加一个progressbar，这样我们就可以很快找到答案。你知道吗

import progressbar

p = progressbar.ProgressBar(widgets=[progressbar.SimpleProgress(), ' ', progressbar.ETA()], maxval=10002)
p.start()

while len(primes) < 10002:
    p.update(len(primes))
    if primeornot(m) is True:
        primes.append(m)
        m=m+1
    else:
        m=m+1

通过这样做，我们可以看到您当前的实现对于这个问题来说太慢了。你需要一个更好的算法。一般来说，我建议实现类似Sieve of Eratosthenes的东西。你知道吗

或者

另一方面，也许我们可以对你的程序做一个小的调整来解决这个问题。让我们看看primeornot()函数。你知道吗

一旦我们找到一个数的实际除数，我们就不需要测试剩余的可用数。相反，我们可以早点回来。所以我们可以：

def primeornot(n):
    for number in xrange(2,n):
        if n % number == 0:
            return False
    return True

另外，我们知道一个数的最大可能除数是square root of that number。所以我们也可以添加优化：

def primeornot(n):
    maximum = int(math.sqrt(n)) + 1

    for number in xrange(2, maximum):
        if n % number == 0:
            return False
    return True

这会导致代码在不到一秒钟的时间内运行，并生成正确的答案。你知道吗