素数判断c语⾔程序分析,C语⾔判断⼀个数是否为素数⽅法解
析
⼀、概念介绍
素数⼜称为质数。⼀个⼤于1的⾃然数(从2开始)，除了1和它本⾝外，不能被其他⾃然数整除的叫做素数，否则称为合数。
0和1既不是素数也不是合数，最⼩的素数是2。
⼆、代码
⽅法⼀：
bool is_Prime(int num){
int i;
for(i = 2;i <= sqrt(num);i++){
if(num % i == 0)//⼀旦发现有因⼦，则返回false
return false;
}
return true;
}
注意：在for循环判断时不能忘记 i <= sqrt(num) 的等号，因为假设 p*p = n , n的因⼦是可以取到 sqrt(n) 的，如判断 9 是不是素数，如果没有等号会出现 9是素数，⽽实际上 9不是素数。
⽅法⼆：
关于质数分布的规律：⼤于等于5的质数⼀定和6的倍数相邻。例如5和7，11和13,17和19等等；
证明：令x≥1，将⼤于等于5的⾃然数表⽰如下：
··· 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1)，6(x+1)+1 ···
可以看到，不和6的倍数相邻的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们⼀定不是素数，再除去6x本⾝，显然，素数要出现只可能出现在6x的相邻两侧。因此在5到sqrt(n)中每6个
数只判断2个，时间复杂度O(sqrt(n)/3)。
在⾼配版和尊享版中，都是⼀个剪枝的思想，⾼配版中裁剪了不必要的偶数，尊享版中裁剪了不和6的倍数相邻的数，虽然都没有降低时间复杂度的阶数，但都⼀定程度上加快了判断的速度。
/*⼀种⾼效的⽅法*/
bool isPrime_3(int num){
//两个较⼩数另外处理
if(num == 2 || num == 3)
return true;
//不在6的倍数两侧的⼀定不是质数
if(num % 6 != 1 && num % 6 != 5)
return false;
int i;
//在6的倍数两侧的也可能不是质数
for(i = 2;i <= sqrt(num);i += 6){
if(num % i == 0 || num % (i + 2) == 0)
return false;
}
//排除所有，剩余的是质数
return true;
}
三、测试
对负数与0，1进⾏异常处理
int main(){
int num;
bool result1,result2;
printf("请输⼊⼀个正整数，以-1结束： ");
scanf("%d",&num);
while(num < 2 && num != -1){
printf("输⼊不合法，请重新输⼊！(说明：素数必须⼤于1)\n"); printf("请输⼊⼀个正整数，以-1结束： ");
scanf("%d",&num);
}
while(num >= 2 && num != -1){
result1 = isPrime(num);
result2 = isPrime_3(num);
if(result1 == true)
printf("%d 是素数\n",num);
else if(result1 == false)
printf("%d 不是素数\n",num);
if(result2 == true)
printf("%d 是素数\n\n",num);
else if(result2 == false)
printf("%d 不是素数\n\n",num);
printf("请输⼊⼀个正整数，以-1结束： ");
scanf("%d",&num);
while(num < 2 && num != -1){
printf("输⼊不合法，请重新输⼊！(说明：素数必须⼤于1)\n");
printf("请输⼊⼀个正整数，以-1结束： ");
scanf("%d",&num);
}
}
c++判断素数}
四、截图
到此这篇关于C语⾔判断⼀个数是否为素数⽅法的⽂章就介绍到这了，更多相关C语⾔判断⼀个数是否为素数内容请搜索脚本之家以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持脚本之家！

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。