素数问题自己之前也接触过，这里做一个系统的总结:

一、素数的判断

首先要明白什么是素数：素数就是只能被1和自己整除的整数，不符合该条件的称为合数；

所以当我们判断一个数是否是素数的时候，最直接粗暴的算法就是对2~n-1进行枚举，如果存在约数k，满足n%k=0;

此时，这个数就不是素数，为合数；

但是该方法的时间复杂度到达了O(n)，我们可以依据数学的特性进行化简；

对于一个k，我们可以由n/k=n/k变形为k*(n/k)=n，如果k满足n%k=0，则n%(n/k)=0也满足，因为n/k也为n的一个约数，对于k和n/k，必有一个小于sqrt(n)。所以对于我们来说，没必要枚举那么多，只需要枚举2~sqrt(n)范围，其中sqrt(n)向下取整；

此时算法那就优化到了O(sqrt(n));所以判断素数的代码如下所示;

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

二、素数表

所谓素数表就是罗列出给定范围内的素数；对于该问题，最简单的就是罗列范围内的每一个数，判断其是否为素数；时间复杂度大概是O(n)*O(sqrt(n));

对于该问题，有更好的算法，称为埃氏筛法，核心就是一个筛字；

对于给定的序列，从2开始枚举，当一个数为素数的时候，剔除给定序列范围内2的倍数。并且每一步筛完之后遇到的第一个数必为素数（原因是如果不为素数，则证明有更小的因子，这和前面的操作冲突）;该算法复杂度为O(nloglogn)

const int maxn=101;int prime[maxn],pNum=0;bool p[maxn]={0};void find_prime(){    for(int i=2;i

我们可以利用vis bool数组来进行甄别该元素是否为素数；