Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

筛的太粗暴了，另外ad都是奇数的话，没必要算a+d, a + 3d这些，肯定都是偶数

Posted by Eov_Second at 2016-11-26 23:10:43 on Problem 3006
In Reply To:同样是素数筛法，为什么我的266ms，心痛！哪位大侠能把我看看哪里可以节约时间吗？ Posted by:guojiale at 2015-06-19 13:06:02

1.筛法没必要筛偶数
2.如果k是素数，则从k*k开始筛，因为3k，5k...这些之前已经筛过了
3.每次递增2k，因为一开始k*k是奇数，再加k，3k..就是偶数了，没必要
所以循环可以写成下面的样子
for(i = k * k; i < ubound; i+=2k)

Followed by:

Post your reply here: