数学-数论-素数筛

Posted by

定义

素数筛用于求出\([2,n]\)范围内的质数。

求解算法

埃拉托斯特尼筛法

思路与简单证明

将\([0,\sqrt n]\)范围内质数的所有\(\leq n\)的倍数筛掉,剩下的就是质数。

时间复杂度\(O(n\log\log n)\)。

实现

欧拉筛

思路与简单证明

枚举\([2,n]\)范围内的所有数\(i\),枚举\([2,i]\)范围内的所有质数\(pri_j\),将\(i\cdot pri_j\)筛掉;

枚举\(pri_j\)时,满足\(i\ mod\ pri_ j\)时终止,因为此时\(i\)可以表示为\(pri_j\cdot x\),之后的数\(i\cdot pri_{j+k}\)可以表示为\(pri_j\cdot x\cdot pri_{j+k}\),已经被\(pri_j\cdot x\)筛掉了,这样可以完全避免一个数被重复筛掉。

时间复杂度\(O(n)\)。

实现

2 comments

Leave a Reply

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