如何判断素数?

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(1)

题目要求:输出100-200的素数

首先我们要知道什么是素数(质数),以防有人忘记(比如刚学开始学c的我就忘记了)

素数(质数)只能被1和它自己整除

7只能被1和7整除,是素数

9能被3整除,不是素数

方法1—试除法

#include<stdio.h> int main() { int i=0; int count=0; for(i=100;i<=200;i ) { int j=0; for(j=2;j<i;j ) { if(i%j==0)//i可以整除j,i不是素数 { break; } } if(j==i)//i只能整除它自己,是素数 { count ; printf("%d ",i); } } printf("\ncount=%d\n",count);//计算100-200之间有几个素数 return 0; }

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(2)

这个代码比较死,只是输出了100到200之间的素数,完成了题目的要求

我们可以把它改造成输入一个数字,判断是否是素数的形式

代码改造1-1

用户输入一个数字

代码判断是否为素数

是,输出“是素数”以及用户输入的值

不是,输出“不是素数”

#include<stdio.h> int main() { int i=0; int j=0; scanf("%d",&i); for(j=2;j<i;j ) { if(i%j==0) { printf("不是素数\n"); break; } } if(j==i) { printf("是素数,i=%d\n",i); } }

结果如下:

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(3)

上面的这串代码能很好地完成我们的需求,但它还有优化的空间

方法2—开平方法

方法1中的for循环为j<i

如果数字很大的话,要循环非常多次才能出现j==i的情况

这就拖慢了我们程序运行的速度

这里我们引入一个概念

若i=a*b

a和b中至少有一个数字 <= 开平方i

如16=2x8=4x4

其中2<4

这样就能得到一个结论:

在根号i之前一定有一个数字n是非素数的除数

如果找不到这个数字n,说明该数字为质数

利用开平方法,我们可以将需要查找的数字范围缩小很多

以下是用该方法完成开头题目要求的代码示例:

#include<stdio.h> int main() { int i=0; for(i=101;i<=200;i =2) { int j=0; for(j=2;j<=sqrt(i);j ) { if(i%j==0) { break; } } if(j>sqrt(i)) { printf("%d ",i); } } return 0; }

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(4)

将这个代码改造成1-1那种形式也不难,自己试试吧!

感谢你看到最后!希望能够帮到你~

-----------------------------------

为了帮助大家,轻松,高效学习C语言/C ,给大家分享我收集的资源,从最零基础开始的,帮助大家在学习C语言的道路上披荆斩棘!

编程学习书籍分享:

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(5)

编程学习视频分享:

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(6)

用c语言编程判断是否为素数(如何判断一个数字是否为素数)(7)

整理分享(多年学习的源码、项目实战视频、项目笔记,基础入门教程)最重要的是你可以在群里面交流提问编程问题哦!

对于C/C 感兴趣可以关注小编在后台私信我:【编程交流】一起来学习哦!可以领取一些C/C 的项目学习视频资料哦!已经设置好了关键词自动回复,自动领取就好了!

,