素数判断？这不是小学学的吗？

您先别着急，不管您是小学，初中还是高中，从事什么职业，我相信，坚持看完你一定有收获！

对你有帮助别忘了给我点个赞哦~

我们要判断素数，首先要知道素数的定义。

知道了素数的定义，那么我们应该想一下，如何去判断一个数是否为素数？

以下除了第一种方法，第2~4种方法都是用第二种思路做的当要判断的目标数很少时，第一种高效。但是当给定的目标数组很多，数也很大时。后面的思路配上高效的查找算法，显然更高效

方法1：暴力求解

1-1:稍微动动脑

思想：根据素数的定义思考。素数是大于1的自然数，除了1和自身外，其他数都不是它的因子。那我们就可以用一个循环，从2开始遍历到这个数减去1，如果这个数都不能被整除，那么这个数就是素数。也就是说：给定一个数n,i从2开始取值，直到n-1(取整数),如果n%i!=0,n就是素数进一步思考，有必要遍历到n-1吗？除了1以外，任何合数最小的因子就是2，那最大的因子就是n/2那我们就遍历到n/2就足够了

这样我们就可以写出这个算法的核心代码：

intisPrime(inttarget){inti=0;if(target=1){printf("illegalinput!\n");//素数定义return-1;}for(i=2;itarget/2;i++){if(target%i==0)return0;//不是素数直接返回0}return1;//是素数返回1}

1-2：再进一步

思想：在上面的基础上，其实不需要遍历到n/2，只需要到根号n（包含根号n）就可以了。为什么呢？这是个数学问题，大家自行思考一下。

核心代码：

intisPrime(inttarget){inti=0;if(target=1){printf("illegalinput!\n");//素数定义return-1;}for(i=2;i=sqrt(target);i++){if(target%i==0)return0;}return1;}

从第二种方法开始，我们都是先完成判断素数数组，然后用二分法去查找判断数组

这里说一下以下三种方法牵扯的概念：

范围：1~范围上限N

范围上限N：判断素数需要用户输入随机素数，这个随机素数的范围是1~N

判断素数数组：将数组的下标与1~N的自然数一一对应起来。判断1到N的自然数是否为素数，其实就是判断数组的下标是否为素数，如果是给这个下标所对应的判断素数数组元素赋1，否则赋0比如：我要判断3是否为素数，我们就找到判断素数数组isPrime中的下标为3的元素，即：isPrime[3]如果3是素数isPrime[3]=1否则isPrime[3]=0这样我们在用二分法查找时，查找数组下标就可以，找到下标后返回下标对应的判断素数数组的值。如果是1说明下标对应的自然数是素数，否则不是

方法2：用素数表来判断素数

思路：如果一个数不能整除比它小的任何素数，那么这个数就是素数这种“打印”素数表的方法效率很低，不推荐使用，可以学习思想

核心代码：

//target：输入的要查找的数//count：当前已知的素数个数//PrimeArray：存放素数的数组intisPrime(inttarget,intcount,int*PrimeArray){inti=0;for(i=0;icount;i++){if(target%PrimeArray[i]==0)return0;}return1;}

方法3：普通筛法——埃拉托斯特尼(Eratosthenes)筛法

核心代码：

//判断素数的数组范围上限NvoidEratprime(int*isprime,intupper_board){inti=0;intj=0;//初始化isprimefor(i=2;i=upper_board;i++)isprime[i]=1;for(i=2;isqrt(upper_board);i++){if(isprime[i]){isprime[i]=1;}for(j=2;i*j=upper_board;j++){//素数的n倍（n=2）不是素数isprime[i*j]=0;}}}

方法4：线性筛法——欧拉筛法

思路:我们再思考一下上面的埃拉托斯特尼筛法，会发现，在“剔除“非素数时，有些合数会重复赋值。这样就会增加复杂度，降低效率。比如：范围上限N=16时2是素数，剔除”2的倍数“，它们是：4，6，8，10，12，14，163是素数，剔除”3的倍数”，它们是，6，9，12，156，12是重复的。如何减少重复呢？

核心代码：

voidPrimeList(int*Prime,bool*isPrime,intn){inti=0;intj=0;intcount=0;if(isPrime!=NULL){//确保isPrime不是空指针//将isPrime数组初始化为1for(i=2;i=N;i++){isPrime[i]=true;}}if(isPrime!=NULLPrime!=NULL){//从2遍历到范围上限Nfor(i=2;i=N;i++){if(isPrime[i])//如果下标（下标对应着1~范围上限N）对应的isPrime值没有被置为false，说明这个数是素数，将下标放入素数数组Prime[count++]=i;//循环控制表达式的意义：j小于等于素数数组的个数或素数数组中的每一个素数与i的积小于范围上限Nfor(j=0;(jcount)(Prime[j]*(longlong)i)=N;j++)//将i强制转换是因为vs上有warning，要求转换为宽类型防止算术溢出。数据上不产生影响{isPrime[i*Prime[j]]=false;//每一个素数的i倍（i=2）都不是素数，置为false//这个是欧拉筛法的核心，它可以减少非素数置false的重复率//意义是将每一个合数（非素数）拆成2（最小因数）与最大因数的乘积if(i%Prime[j]==0)break;}}}}

如果你没有理解，可以参考下例

​

​

感谢观看，如果有什么错误请指出，谢谢各位！

​有什么不懂也可以直接提出来，我看到就会给大家解答的