首页
学习
活动
专区
工具
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)等。你可以通过访问腾讯云官方网站获取更详细的产品介绍和相关链接。

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

相关·内容

十个提高编码技能的诀窍,你掌握了几个?

你想成为一名程序员,并且正在为之奋斗,那么你努力的方式,比如做事方法、思维习惯都将会影响你会成为怎样的一名程序员。 那么,你需要成为一个天才才能学好编程吗?我觉得没有必要。 你必须建立自己的做事方式。需要学习一些(或更多的)技巧, 不断的在Google上搜索查询,与书成为朋友。有一长串的TODO需要遵循。我将在这里分享一些技巧,帮你提高编程技能。 尽可能多地练习: 坚持练习几个小时听起来很难, 但一旦喜欢上这种方式, 相信我, 你会乐此不疲。你一定听说过熟能生巧。这对程序员来说是非常必要的。   这里有个问题。练习什么?问得好。社会媒体是实践资源的一个重要来源。加入有新手程序员分享他们所面临的问题的群组和论坛,去帮助他们。几乎每本书都有很多经典的案例。不要跳过章节练习。留意实际运用中的问题并且尝试解决掉。 加入开发者社区: 如上所述,社交媒体可以给到你想要的一切。有大型专业社区。有些是非常流行的, 如 StackOverflow 和MSDN。这里有许多技术牛人可以给到你帮助,也有一些新手需要你的帮助。注册 (免费的), 然后扩大你的社交圈。 多吸取建议 允许他人阅读您的代码。如果有批评的观点, 请感谢他们。因为他们将帮助您找到代码中的漏洞,提高代码质量和逻辑。对有些人来说,很难接受批评。我就是其中之一, 但很快我意识到, 评论者正帮助我测试代码。 解决困惑和谜题: 当我还是新手的时候, 我常常解决一些编程难题,直到现在我仍然在周末寻找一些难题并享受解决之后的喜悦。它刺激大脑并保持头脑的运转。 当同样的问题再次出现时,在哪里可以找到解决这些困惑的方法? 下面是一些资源。

01

第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-935 互质数个数

这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍,让大家方便去搜索,所有题目都会有几种语言的写法,帮助大家提供一个思路,当然,思路只是思路,千万别只看着答案就认为会了啊,这个方法基本上很难让你成长,成长是在思考的过程中找寻到自己的那个解题思路,并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练,如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢,这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来,所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式,说着听绕口,但是就是靠量来堆叠思维方式,刷题方案自主定义的话肯定就是从非常简单的开始,稍微对数据结构有一定的理解,暴力、二分法等等,一步步的成长,数据结构很多,一般也就几种啊,线性表、树、图、再就是其它了。顺序表与链表也就是线性表,当然栈,队列还有串都是属于线性表的,这个我就不在这里一一细分了,相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的,例如三分枚举、离散化,图,复杂数据结构还有统计都是不考的,我们找简单题刷个一两百,然后再进行中等题目的训练,当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠,慢慢的就会掌握各种规律,有了规律就能大胆的长一些难度比较高的题目了,再次说明,刷题一定要循序渐进,千万别想着直接就能解决难题,那只是对自己进行劝退处理。加油,平常心,一步步前进。

03
领券