项目Euler #7 Python

Question

我的密码出问题了。问题是：

“通过列出前六个素数: 2、3、5、7、11和13，我们可以看到第6个素数是13。10001素数是什么？”。

看上去是这样的：

div = 10001
i = 2
count = 0
prime = 0
now = []

while count < div:

    for x in range (2,i+1):
        if len(now) ==2:
            break
        elif i%x == 0:
            now.append(x)

    if len(now)==1:
        prime = i
        count += 1
    now = []
    i+=1       



print(prime)

我试过div高达1000，它似乎很好(对于div 1000，我收到7919)。然而，当我尝试div = 10001时，我什么也得不到，甚至没有错误。如果有人帮我，我会很感激的。谢谢。

Answer 1

# 7 10001st prime

import itertools


def is_prime(n):
    for i in range(2, n//2 + 1):
        if n % i == 0:
            return False
        else:
            continue
    return True


p = 0
for x in itertools.count(1):
    if is_prime(x):
        if p == 10001:
            print(x)
            break
        p += 1

Answer 2

试试下面的代码：

prime_list = lambda x:[i for i in xrange(2, x+1) if all([i%x for x in xrange(2, int(i**0.5+1))])][10000]
print prime_list(120000)

Python中的Lambda定义了一个匿名函数，xrange与range类似，定义了一个整数范围。代码使用列表理解，并两次遍历这些数字，直到最后一个数字的平方根(因此，i**0.5)。如果每个数字是范围计数中的数字的倍数，则每个数字都会被消除。您将得到一个按顺序排列的素数列表。所以，你只需要用正确的索引打印数字。

Answer 3

只要对代码进行一些简单的修改(和简化)，您就可以在1/3秒钟内计算要查找的数字。首先，我们只检查@Hashman建议的平方根。接下来，我们只测试并除以奇数，将2作为特例预先处理。最后，我们抛出整个now数组长度逻辑，并简单地利用break逻辑：

limit = 10001
i = 3
count = 1
prime = 2

while count < limit:

    for x in range(3, int(i ** 0.5) + 1, 2):
        if i % x == 0:
            break
    else:  # no break
        prime = i
        count += 1

    i += 2

print(prime)

和以前一样，这给了我们7919的限制，1000，它给了我们104743，我们的极限为10001。但这还不如筛子快。