一、直观判断法
bool isPrime( int num ) {
int temp = sqrt(num);
for (int i = 2; i <= temp; i++) {
if (num % i == 0) return 0;
}
return 1;
}
二、直观判断法优化
https://blog.csdn.net/huang_miao_xin/article/details/51331710
证明
令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。
此时判断质数可以 6 个为单元快进，即将方法一循环中 i++ 步长加大为 6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果 n 能被6i，6i+2，6i+4整除，则 n 至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果 n 能被6i+3整除，则 n 至少能被 3 整除，但是6x能被 3 整除，故6x-1或6x+1（即n）不可能被 3 整除，故不成立。综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为 6，每次判断循环变量 k 和 k+2 的情况即可，理论上讲整体速度应该会是方法一的 3 倍。
代码
bool isPrime(int x) {
if (x == 1 || x == 0) return 0;
if (x == 2 || x == 3) return 1; //两个较小数另外处理
if (x % 6 != 1 && x % 6 != 5) return 0; //不在6的倍数两侧的一定不是质数
//在6的倍数两侧的也可能不是质数
int temp = sqrt(x);
for (int i = 5; i <= temp; i += 6) {
if (x % i == 0 || x % (i + 2) == 0) return 0;
}
//排除所有，剩余的是质数
return 1;
}
三、素数一般筛法（埃拉托斯特尼筛法）
调和级数证明可得复杂度为（nlglgn）,所以不能称之为线性筛，但是它的实际运行速度也不是特别慢
基本思想
素数的倍数一定不是素数
实现方法
用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。
举例
我们筛前20个数
首先初始为（0代表不是素数，1代表是素数）
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
然后从2开始我们发现2被标记为素数，我们把2的倍数全部筛掉
变为：
0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
接着到3我们发现3仍然被标记，把3的倍数全部筛掉
变为：
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
接着一直重复下去就得到了最后的素数表：
0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0
2 3 5 7 11 13 17 19
代码
void isPrime() {
prime[0] = prime[1] = 0;
for (i = 2; i < MAXN; i++) {
if (prime[i]) continue;
for (j = i * i; j < MAXN; j += i) prime[j] = 1;
}
return ;
}
四、线性筛（欧拉筛法）
我们发现在上面的筛法中有的数字是多个素数的倍数，也就是说它可能会被重复计算多次，比如说6同时是2与3的倍数，它在计算时就被访问了两次,这样会导致效率低下，所以在下面的算法中我们考虑如何优化这种情况。
原理
任何一个合数都可以表示成一个质数和一个数的乘积
证明
假设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)的乘积，那样我们到每一个数，都处理一次，这样处理的次数是很少的，因此可以在线性时间内得到解。
仍然按上面的例子模拟（这里0为是素数，1为非素数，p为记录的素数表）：
初始：
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
p(empty)
然后到2的位置，把2放入素数表,做当前范围内可以筛掉的处理（具体是怎样的看代码叭）：
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
p 2 到3，把3放入素数表，继续处理
1 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0
p 2 3 然后到了4，它不是个素数，也处理一下
1 0 0 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0
p 2 3 .......
然后一直搞下去，最后也能得到完整的素数表，这样虽然看起来复杂一些，但是实际上我们发现对于每个数的处理几乎是O(1)的。
代码
#include<stdio.h>
#define MAN_N 1000000
int prime[MAN_N + 5] = {0};//1.标记 2.储存素数 3.prime[0]计数
void isPrime() {
for (int i = 2; i <= MAN_N; i++) {
if (!prime[i]) {
prime[++prime[0]] = i;//储存素数
}
for (int j = 1; j <= prime[0] && prime[j] * i <= MAN_N; j++) {
prime[i * prime[j]] = 1;//标记合数
if (i % prime[j] == 0) break;//遍历到i的最小素数为止
//即比一个合数大的质数和该合数的乘积可用一个更大的合数和比其小的质数相乘得到
}
}
return ;
}
数据较大时
#include <iostream>
#include <cstdio>
using namespace std;
#define MAXN 1005
int prime[MAXN];
int n, p;
void init() {
for (int i = 2; i < MAXN; i++) {
if (!prime[i]) prime[++prime[0]] = i;
for (int j = 1; j <= prime[0] && i * prime[j] < MAXN; j++) {
prime[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}
int check(int x) {
if ((x!=2&&!(x%2)) || (x!=3&&!(x%3)) || (x!=5&&!(x%5)) || (x!=7&&!(x%7))) return 0;
for (int i = 1; i <= prime[0] && prime[i] * prime[i] <= x; i++) {
if (x % prime[i] == 0) return 0;
}
return x > 1;
}
