哥德巴赫猜想(二)

难度:

尊敬的用户,该视频为旧版会员课程,仅限已购买的会员查看

编玩边学最新推出哈克尼斯圆桌课堂模式

更优质的课程与服务,系统的课程体系,提供国内最专业的儿童编程教育

查看新版课程

这节课教大家对质数判别算法进行改进,然后实现程序:判别所有的偶数是否均符合哥德巴赫猜想。


第一步,质数判别算法改进

若n不是素数,则n可表示为a*b,其中2<=a<=b<=n-1,则a一定满足:1<a<=sqrt(n);

因而,只需要用2~sqrt(n)去除n,而不用1~n-1.这样便极大地减少了循环次数,改善了算法效率。


blob.png


第二步,构造哥德巴赫判别函数

在上节课哥德巴赫猜想(一)的代码上进行修改,对歌德巴赫判定的代码封装到哥德巴赫判别函数

定义参数y,即为当前需要进行哥德巴赫判定的数,然后将代码中的“回答”改成参数y的值。

将“符合哥德巴赫猜想成功时说出Y=n1+n2的代码”修改为:猜想成功时,将Y=n1+n2添加到链表goldbach中。

blob.png

第三步,编写主代码,遍历从6开始的所有偶数,并对每一个偶数进行哥德巴赫判别;

blob.png


作业: 

在本节课程序的基础上,实现:每当检验完100个偶数,1000个偶数,10000个偶数时给出检验进度提示.

 

此外,请思考:质数判别算法是否还有改进空间?提示:譬如循环中可以跳过除2外的偶数




 登录/注册后发表或回复问题

在本系列的课程中,我们将经典算法在scratch中实现,你准备好了吗?挑战你自己的时刻到了

通过本系列课程的学习,你将会学到编程的精髓——算法,成为编程专家


###讲课老师:王代银,北大2015级硕士,算法、黑客技术高手,将艰深晦涩的算法问题用scratch讲得有趣易懂,这套scratch算法课程备受众多中小学信息技术课教师推崇,被大量用作参考教材!