项目Euler #10 -素数之和

Question

(来自欧拉项目)

低于10的素数之和为2+3+5+7= 17，求出2百万以下素数之和。

有人能帮我改进一下这段代码吗？

import math

def main():
    lim = 2000000
    i = 2
    now = []
    total = 0
    for i in range(2,lim+1):
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) ==2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
            print(total)
        now = []
    print(total)

Answer 1

第一步:函数和测试

你应该写的第一件事就是计算你真正想要的东西的函数:素数之和。此外，还提供了一个值作为问题的一部分，使用它来编写测试:一旦出现问题，您可能会注意到它。

def sum_primes_to_limit(lim):
    i = 2
    now = []
    total = 0
    for i in range(2,lim+1):
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) ==2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
        now = []
    return(total)

def main():
    assert sum_primes_to_limit(10) == 17
    print(sum_primes_to_limit(2000000))

使事情变得更简单

不需要声明i变量。类似地，不需要在循环之前定义now变量，并在每次迭代结束时清除它:只需在每次迭代时将其定义为空。

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        now = []
        for x in range(1,int(math.sqrt(i))+1):
            if len(now) == 2:
                break
            elif i % x == 0:
                now.append(x)

        if len(now) == 1:
            total += i
    return(total)

使事情变得更简单

您并不真正关心now的内容，只关心它的长度。而且，没有必要在每次迭代时检查它不会超过2:只需在更新列表时检查一下。

此外，您还可以去掉列表并使其成为一个简单的计数器：

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        nb_div = 0
        for x in range(1,int(math.sqrt(i))+1):
            if i % x == 0:
                nb_div += 1
                if nb_div == 2:
                    break

        if nb_div == 1:
            total += i
    return(total)

多功能

考虑到检查数字是否为素数的方式，为此定义一个函数可能是有意义的：

def is_prime(i):
    nb_div = 0
    for x in range(1,int(math.sqrt(i))+1):
        if i % x == 0:
            nb_div += 1
            if nb_div == 2:
                return False
    return nb_div == 1

def sum_primes_to_limit(lim):
    total = 0
    for i in range(2,lim+1):
        if is_prime(i):
            total += i
    return(total)

一段Python酷语法

Python中最酷的是生成器表达式。使用生成器表达式和sum，您可以以简洁而奇特的方式编写sum_primes_to_limit：

def sum_primes_to_limit(lim):
    return sum(i for i in range(2,lim+1) if is_prime(i))

重写函数

如果您只从2开始，就可以避免将1视为除数(然后，您可能需要对1进行一些特殊处理，但我将把它留给您处理)。

然后你的功能变成：

def is_prime(i):
    nb_div = 0
    for x in range(2,int(math.sqrt(i))+1):
        if i % x == 0:
            nb_div += 1
            if nb_div == 1:
                return False
    return nb_div == 0

那么，你不再需要这个号码了：

def is_prime(i):
    for x in range(2,int(math.sqrt(i))+1):
        if i % x == 0:
            return False
    return True

这看起来真的很想用生成器表达式(这次是all或any )来编写。

def is_prime(i):
    return all(i % x for x in range(2,int(math.sqrt(i))+1))

(请注意，我利用这个机会删除了!= 0，因为非零布尔值将计算为True)。

，这一切都很酷，但我们需要速度！

您想要计算/检查素数到一定的限度。好消息是，有一个算法就是这样的：埃拉托斯提尼筛。

下面是一个实现：

def sieve(lim):
    primes = [True] * (lim+1)
    primes[0] = primes[1] = False
    for i in range(2, int(math.sqrt(lim))+1):
        if primes[i]:
            for j in range(i*i, lim+1, i):
                primes[j] = False
    return primes

def sum_primes_to_limit(lim):
    primes = sieve(lim)
    return sum(i for i in range(2,lim+1) if primes[i])

最终细节

我已经习惯了Python3，但是如果您使用Python2，range会生成一个实际的列表。当这不是必需的(在您的情况下，这不是必需的)时，您应该使用xrange。