素数（打表，判断，快速打表）

1： 素数被称为质数，是指除了1之外和本身之外，不能被其他数整除的一类数。否则，就可称为合数。

注意：1既不是素数也不是合数。

本博客要解决两个问题：

1；如何判断一个数是素数？

2：如何在最短时间内得到1~n之间的素数表？

一、素数的判断。

一个整数n要被判断为不是素数，就需要判断2~n-1中是否有数能被整除，只要有一个能被整除就不是素数。

代码：bool isprime(int n){
if(n<=1){
return false;
}
for(int i = 2 ;i < n;i++){
if(n%i==0)return false;
}
return true;
}

然后知道此代码的时间复杂度为O(n)，但是在很多的题中求素数只是一部分，所以很容易超时。有一个快速的方法：

注意到2_{n-1中存在n的约数，不妨设为k，即n%k==0，那么由k*(n/k)==n可知，n/k也是n的一个约数且k与n/k中一定满足其中一个小于等于sqrt（n).另一个大于等于sqrt（n），这启发我们只需判断2}sqrt（n）之间的数就行。该算法的时间复杂度为O(sqrt(n))。

代码：bool isprime(int n){
if(n<=1){
return false;
}
int k=(int)sqrt(1.0*n);
for(int i = 2 ;i <= k;i++){
if(n%i==0)return false;
}
return true;
}

在上面的代码中，sqrt的作用为一个浮点数开根号，需要加math.h头文件。

如果没有接近int型的变量的范围上界，那么有更简单的写法：

bool isprime(int n){
if(n<=1){
return false;
}
for(int i = 2 ;i*i <= n;i++){
if(n%i==0)return false;
}
return true;
}

这样写时会导致当n接近int上界时i*i会溢出（当然n在10 的9次方以内还是安全的），解决的方法是将i定义为long long型这样就不会溢出了。

二、 素数表的获取。

既然你就知道了素数的判断方法，那么你就可以枚举1~n之间的素数这种方法的枚举部分的复杂度是O(n)，而判断素数的复杂度是O(sqrt(n)),因此总复杂度就是O(n*sqrt(n))。这个复杂度解决10的5次方以内的数是没有问题的。

代码：bool isprime(int n){
if(n<=1){
return false;
}
for(int i = 2 ;i*i <= n;i++){
if(n%i==0)return false;
}
return true;
}
const int maxn = 110;
int prime[maxn] ,pNum = 0;
bool p[maxn] = {0};//p[i]=true表示i就是素数
void find_prim(){
for(int i =1;i<maxn;i++){
if(isprime(i)==true){
prime[pNum++] = i;
p[i] = true ;
}
}
}

上面的算法在10的5次方以内是可以承受的，但是出现大范围的素数表了怎么办？有一个更高效的方法，它的时间复杂度为O(nloglogn)。

‘埃式筛法’是众多筛法中最简单跟容易理解的方法，更优的欧拉算法可以达到O(n)，方法就是判断出一个素数n，然后就是乘以1倍，2倍，3倍的方法一个一个的筛选，知道筛选完全。

至于筛的这个动作的实现，可以使用一个bool数组进行标记，如果p[a]为true，则不是素数就是被筛掉的数；否则，

p【a】为false，初始化是全为false。

代码：const int maxn = 101;
int prime[maxn],pnum=0;
bool p[prim] = {0};
void find_prim(){
for(int i=2;i<maxn;i++){
if(p[i] ==false){
prim[pnum++]=i;
for(int j=i+i;j<maxn;j=j+i){
p[j]=true;
}
}
}
}