共计 889 个字符，预计需要花费 3 分钟才能阅读完成。
素数问题自己之前也接触过，这里做一个系统的总结:
一、素数的判断首先要明白什么是素数：素数就是只能被 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<maxn;i++){
if(p[i]==false){
prime[pNum++]=i;
for(int j=i+i;j<maxn;j+=i){
p[j]=true;
}
}
}
}
我们可以利用 vis bool 数组来进行甄别该元素是否为素数；
