首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

Project Euler任务#10 Python错误答案

Project Euler是一个面向数学和计算机科学爱好者的在线编程挑战平台。任务#10要求计算出小于给定数值的所有质数的和。下面是一个Python的错误答案:

代码语言:txt
复制
def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

def sum_of_primes(limit):
    sum = 0
    for i in range(2, limit):
        if is_prime(i):
            sum += i
    return sum

print(sum_of_primes(2000000))

这段代码的目标是计算小于2000000的所有质数的和。然而,这段代码存在一个性能问题,导致计算时间过长。在每次判断一个数是否为质数时,都需要遍历从2到该数的平方根的所有数,这会导致计算时间呈指数级增长。

为了优化这段代码,可以使用埃拉托斯特尼筛法(Sieve of Eratosthenes)来找出小于给定数值的所有质数。该算法的基本思想是从2开始,将每个质数的倍数标记为非质数,直到遍历完所有小于给定数值的数。下面是优化后的代码:

代码语言:txt
复制
def sum_of_primes(limit):
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(limit**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, limit, i):
                is_prime[j] = False
    return sum(i for i, prime in enumerate(is_prime) if prime)

print(sum_of_primes(2000000))

这段代码使用了一个布尔数组is_prime来表示每个数是否为质数。初始时,将所有数都标记为质数。然后从2开始遍历,如果当前数为质数,则将其倍数标记为非质数。最后,将所有质数的索引相加即可得到结果。

推荐的腾讯云相关产品:腾讯云函数(Serverless Cloud Function),腾讯云容器服务(Tencent Kubernetes Engine),腾讯云数据库(TencentDB),腾讯云对象存储(Tencent Cloud Object Storage),腾讯云人工智能(Tencent AI),腾讯云物联网(Tencent IoT),腾讯云移动开发(Tencent Mobile Development)等。你可以通过访问腾讯云官方网站获取更详细的产品介绍和相关链接。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券