算法 求素数（三种方法.线性筛选法）

算法 求素数（三种方法.线性筛选法）

用筛选法求100之内的素数

1. 求素数

最初的素数比较暴力，也只是能判断一个数是不是素数或者求n以内的素数个数，用最朴素的算法来写就是下面这样的

#include <stdio.h>
int main(){int a=0;  // 素数的个数int num=0;  // 输入的整数printf("输入一个整数：");scanf("%d",&num);for(int i=2;i<num;i++){if(num%i==0){a++;  // 素数个数加1}}if(a==0){printf("%d是素数。n", num);}else{printf("%d不是素数。n", num);}return 0;
}

这种算法时间复杂度是o(n*sqrt(n))，用这种方法，当n很大的时候，比如n=10000000时，n*sqrt(n)>30000000000,数量级相当大。在一般的机子它不是一秒钟跑不出结果，它是好几分钟都跑不出结果。

2.普通筛选法求素数(埃拉托斯特尼筛法)

1.开一个大的bool型数组arr[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为0.

3.最后输出arr数组中的值为1的单元的下标，就是所求的n以内的素数了。 

原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质数的倍数筛掉。

一个简单的筛素数的过程：n=30。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

第 1 步过后2 4 ... 28 30这15个单元被标成0,其余为1。

第 2 步开始：
　　i=3; 由于arr[3]=1, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为0.
　　i=4; 由于arr[4]=0,不在继续筛法步骤。
　　i=5; 由于arr[5]=1, 把arr[10],[15],[20],[25],[30]标为0.
　　i=6>sqrt(30)算法结束。
第 3 步把arr[]值为1的下标输出来：

for(i=2; i<=30; i++)if(arr) printf("%d ",i);

结果是 2 3 5 7 11 13 17 19 23 29

        这就是最简单的素数筛选法，对于前面提到的10000000内的素数，用这个筛选法可以大大的降低时间复杂度。

算法复杂度O(N*LogN)

代码如下：

#include <stdio.h>
#define N 200/*定义最大数*/int main() {double s, t;int arr[N + 1] = { 0 };int j = 2;//定义起始数，从2开始int i;//计数器for (i = 2; i < N + 1; i++) {arr[i] = i;//待筛选数组赋值}for (i = 2; i < N + 1; i++) {j = 2;while (j * i < N + 1) //不符合条件的数字筛除{arr[j * i] = 0;j++;}}for (i = 2; i < N + 1; i++) {//输出if (arr[i] != 0)printf("%-5d", arr[i]);}return 0;
}

        很明显，我们可以对上面的代码进行优化，判断每个数是不是素数，如果是素数，素数的倍数标记为非素数，如果不是素数，不做处理，因为非素数的倍数一定会在这个非素数之前被处理了，没必要重复处理。代码如下： 

#include <stdio.h>
#define N 10000000//定义最大数int main() {double s, t;int arr[N + 1] = { 0 };int j = 2;//定义起始数，从2开始int i;//计数器for (i = 2; i < N + 1; i++) {arr[i] = i;//待筛选数组赋值}for (i = 2; i < N + 1; i++) {j = 2;while (j * i < N + 1) //不符合条件的数字筛除{arr[j * i] = 0;j++;}}for (i = 2; i < N + 1; i++) {//输出if (arr[i] != 0)printf("%-5d", arr[i]);}return 0;
}

　3.线性筛选法求素数（欧拉筛法）

　　a.原理：

      i. 任何一个合数都可以表示成一个质数和一个数的乘积
      ii. 假设A是一个合数，且A = x * y，这里x也是一个合数，那么有:
        A = x * y; (假设y质数，x合数)
        x = a * b; (假设a是质数，且a < x)   =》 A = a * b * y = a * Z (Z = b * y)
　　即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积

         b.代码：

#include<stdio.h>
#include<cstring>
#define N 100
const int maxn = 1e5 + 5;
int prime[maxn];
bool vis[maxn];
void sieve(int n)
{int cnt = 0;for (int i = 2; i <= n; i++){if (!vis[i]) //不是目前找到的素数的倍数prime[cnt++] = i; //找到素数for (int j = 0; j < cnt && i * prime[j] <= n; j++){vis[i * prime[j]] = true; if (i % prime[j] == 0) break; } }for (int k = 0; prime[k] != NULL; k++)printf("%d ", prime[k]);//从素数数组输出素数
}
int main()
{memset(vis, false, sizeof vis);sieve(N);return 0;
}