时间戳

首页 > 解决方案 > Project Euler 任务#10 Python 错误答案

python - Project Euler 任务#10 Python 错误答案

问题描述

欧拉计划#10的任务是： 10 以下的素数之和为 2 + 3 + 5 + 7 = 17。求所有低于 200 万的素数之和。

我很困惑为什么我的代码给了我一个错误的答案1000000000001。这里是：

def prime(a):
    for i in range(2,a):
        if a % i == 0:
            return False
            break
        return True

sum = 2
for n in range(3,2000000,2):
    if prime(n):
        sum += n
print(sum)

有人可以解释一下它到底有什么问题吗？

标签： python

解决方案

您从 for 循环中返回得太早：

def prime(a):
    if a < 2:
        return False
    if a == 2:
        return True
    for i in range(2,a):
        if a % i == 0:
            return False
    # should be after checking all numbers
    return True # this line

此外，您只需要检查sqrt(a)并排除偶数。

import math

# skip even numbers
def prime(a):
    if a == 2:
        return True
    if a % 2 == 0:
        return False
    n = math.ceil(math.sqrt(a))
    for i in range(3, n+1, 2):
        if a % i == 0:
            return False
    return True

推荐阅读