PRIME1解题笔记

前几天JeffChen告诉我他要学习Python,后来他找到了SPOJ这个在线的算法竞赛网站,可以支持很多种不同的编程语言,其中包括Python。而我突然发现我很久以前就注册了我的帐号,现在一下又来了兴趣。虽然在中学的时候也搞过信息学奥赛,不过没有出过江苏省,和ACM的差距还是非常非常大。因为我数学功底不行,这方面没法深入,所以转投应用领域,加上很懒,所以喜欢用脚本语言。

言归正传,下面把我解决PRIME1这道问题的方法记录下来:

求质数最经典的方法是Eratosthenes筛选法,一般都是利用一个布尔数组作为筛选器,将下标作为目标数,元素作为该目标是否为质数的标志,并且对于给定范围1~n之间的数,只需要筛选掉1到sqrt(n)之间的质数的所有倍数,剩下的就都是质数了。

起初我使用Python是直接利用range函数生成列表,并没有用到筛选表,通过filter函数和取模%筛选掉质数,最后直接得到整个列表。但是问题在于性能低,另外对于大数则会内存不够(无法生成给定长度的列表),我也尝试过使用dict对象来建立筛选器,不过都失败了。

问题关键在于Python是脚本语言,对于速度,尤其是列表的遍历,不应该使用filter或者for循环,应该使用列表理解,,并且抛弃%运算,配合python列表的slice语法,即x[start:end:step]=[…]的方法,进行定长步长(以质数为步长)的批量替换。

对于内存不够,可以建立一个映射关系,最后的筛选数组中,不考虑偶数,把奇数转换成筛选数组的索引(n/2-3),但需要一些算法精确配合上面的slice语法计算起始位置和长度。

“PRIME1解题笔记”的4个回复

  1. hi,能把你的代码给我看看吗 我用C实现的AC了 但是python一直超时 我才接触python一周 很多优化的地方都不是很清楚 你说的slice语法也不是很熟悉;-) 谢谢了~

发表评论

电子邮件地址不会被公开。 必填项已用*标注