质数筛

质数筛

若一次判断很多数时，用到素数筛，将 2～n 没个数进行枚举，看哪些数是它的约数，将它乘上某个数(枚举倍数)：2i，3i···直到 > n，未被标记(除本身无其他约数)即质数

为什么是 nlogn 级别？

看每个数枚举的次数，2 大概\frac{n}{2}，3\frac{n}{3}···统一提 n 即有：n(\frac{1}{2}+\frac{1}{3} +··· +\frac{1}{n})，其中(\frac{1}{2}+\frac{1}{3} +··· +\frac{1}{n})为调和级数，logn

#include <iostream>


using namespace std;


bool not_prime[200];


int main()
{
    int n = 100;
    for(int i = 2; i <= n; ++ i)
        for(int j = 2 ;i * j <= n ; ++ j)
        not_prime[i * j] = true;
    for(int i = 2; i <= n; ++ i) if(!not_prime[i]) cout << i << endl;
    return 0;
}

质数筛

朴素筛法：从前往后，依次将每个数倍数删掉，则最后剩余即质数

证明：若其中一个数为P，P此时留下，那么说明有2～P-1都没有把P删除，P不是2～P-1任何一个数的倍数，2～P-1不存在P的约数

时复分析：i = 2时，循环\frac{n}{2}次，3循环····n循环，得到公式后将n提出，则有n(\frac{1}{2}+ \frac{1}{3} + ··· + \frac{n}{n})，当n趋紧正无穷，后面调和级数 = lnn + c级别(c是欧拉函数0.577··)，则\approxn *lnn

底数越大log数越小，则有