首页 > 代码库 > C语言判断一个数是否是素数
C语言判断一个数是否是素数
素数又称质数。所谓素数是指除了1和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被2~16的任一整数整除。
思路1)：因此判断一个整数m是否是素数，只需把m被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么m就是一个素数。
思路2)：另外判断方法还可以简化。m不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ 
之间的每一个整数去除就可以了。如果m不能被 2 ~ 间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。
原因：因为如果m能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于，另一个大于或等于。例如16能被2,4,8整除，16=2*8，2小于4，8大于4，16=4*4，4=√16，因此只需判定在2~4之间有无因子即可。
思路1：
1 int IsPrime(int x) 2 { 3 int i,a ; 4 for(i=2;i<x-1;i++) //从2到x-1看看能不能被整除 5 { 6 a=x%i; 7 if(a==0) //整除 说明不是素数 ，返回2， 8 {return 2;break;} 9 }10 if(i==(x-1))//整个for循环结束，循环到最后也没整除，说明是素数 返回111 return 1; 12 }
思路2:
1 int IsPrime2(int x) 2 { 3 int i,a ; 4 if(x==2)return 1; 5 for(i= int (sqrt(x));i>2;i--) //从2到x-1看看能不能被整除 6 { 7 a=x%i; 8 if(a==0) //整除 说明不是素数 ，返回2， 9 {return 2;break;}10 }11 if(i==2)//整个for循环结束，循环到最后也没整除，说明是素数 返回112 return 1; 13 }
C语言判断一个数是否是素数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。