素数筛法模板

为什么只遍历到sqrt(n)就够了？

反证法:
假设只遍历2～sqrt(n)不能把所有非素数置为false，即遍历完了2～sqrt(n)后，在sqrt(n)～n范围内仍有一个非素数k，但isprime[k]=true。

证: k在sqrt(k)之前一定有一个素数因子(任何非素数都可以拆成素数的乘积，所以k至少有一个素数因子)，sqrt(k)肯定小于sqrt(n)，所以sqrt(n)之前一定有一个k的素数因子y，那么根据代码中的算法，i=y的时候，k肯定会被置为非素数，即此时isprime[k]就会被置为false，原假设不成立。
因此只需遍历2～sqrt(n)即可。

此方法时间复杂度为O(n*loglogn)，空间复杂度为O(n)

 1 #include <iostream>
 2 #include <cmath>
 3 
 4 using namespace std;
 5 
 6 #define MAXN 10000
 7 int prime[MAXN+10];     // 保存筛得的素数
 8 int primeSize;          // 保存素数的个数
 9 bool mark[MAXN+10];     // 若mark[i]为true，表示i被标记为素数 
10 
11 void init()
12 {
13     for(int i = 2; i <= MAXN; ++i)
14         mark[i] = true;        // 初始化，所有数字均被标记为素数
15     primeSize = 0;
16     int m = sqrt(MAXN+1);    // sqrt函数比较耗时，所以这里把它提到循环外面
17     for(int i = 2; i <= m; ++i)
18     {
19         if(mark[i] == true)
20         {
21             prime[primeSize++] = i;
22             for(int j = i*i; j <= MAXN; j += i)    
23                 mark[j] = false;    // 该数的所有倍数都不是素数 
24         } 
25     } 
26 }
27

素数筛法 模板

素数筛法模板