素数与筛法

 质数判别

sqrt判别　　O（√N）

素数筛法

1.埃式筛法  O（nloglogn） 筛法

   就是找到一个质数，把它的倍数全部标记为合数（但是你会发现有的数字会被标记多次，比如 6     被     2，3都标记，这样会浪费时间。。）

 2.线性筛法

   Ps:  1+1/2+1/3+1/4+......+1/n  这样的时间复杂度是 log n

   线性筛法保证了每个数只会被他的最小质因子标记

  举个栗子：

   i = 5^3 * 7^2

   i2=5 * 5^3 * 7^2

    i3=3 * i2

     i4=2 * i3

从最小质因子开始，一直×到最小的2

素数与筛法

原文：https://www.cnblogs.com/xiaoyezi-wink/p/10657881.html