如何判断素数

题目要求：输出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;}

这个代码比较死，只是输出了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);}}

结果如下：

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

方法2—开平方法

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

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

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

这里我们引入一个概念

若i=a*ba和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;}

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