APTX Blog

A Moe Blog Set By APTX

C/C++线性筛素数的三种方法

一、埃拉托斯特尼筛法

基本思想:素数的倍数一定不是素数

实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。

说明:整数1特殊处理即可。背过就好了。

时间复杂度O(nlogn)

空间复杂度为O(n)

 

二、欧拉筛法(线性筛法)

时间复杂度O(n)

空间复杂度O(n)

三、一个奇怪的筛法

时间复杂度 接近O(n)

 

洛谷:P3383

点赞

发表评论

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