筛法

2021-02-09  本文已影响0人  吴健民IT

素数表的获取

从1~n进行枚举,判断每个数是否是素数,如果是素数则加入素数表,这种方法的枚举部分的复杂度是O(n),而判断素数的复杂度是O(√n),因此总复杂度是O(n√n)。这个复杂度对n不超过10^5的大小是没有问题的,考试时大部分涉及素数表的题目都不会超过这个范围。

这里讲一下“埃氏筛法”:

相比于简单易懂的埃氏筛法,欧拉筛法在理解上面会有些难度,但是它对于同一个数,它并不会将其重复筛去。因此,它的复杂度几乎可以说是真正做到了O(n)的程度。

其中temp = i * primes[ j ] 的思想是:

拿2,3,4,5,6,7,8,9,10,11,12,13,14,15举例

因为5是素数,则5×2=10,5×3=15,5×4=20,5×5=25,(上限为15,所以10,15筛去)

因为6是合数,则6×2=12,6×3=18,6×4=24,6×5=30,(上限为15,所以12筛去)(这里不用6×6)

上一篇下一篇

猜你喜欢

热点阅读