【C语言】如何判断素数
慕雪年华

如何判断素数

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

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

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

  • 7只能被1和7整除,是素数
  • 9能被3整除,不是素数

方法1—试除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
}

image

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

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


代码改造1-1

  • 用户输入一个数字
  • 代码判断是否为素数
  • 是,输出“是素数”以及用户输入的值
  • 不是,输出“不是素数”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#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);
}
}

结果如下:

image

image


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

方法2—开平方法

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

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

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

这里我们引入一个概念

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

如16=2x8=4x4

其中2<4

这样就能得到一个结论:

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

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


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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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;
}

image

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

两个方法分别的弊端

试除法

该方法会错过1

开平方法

该方法会错过2


感谢你看到最后

如果这篇博客对你有帮助,请点赞支持一下,万分感谢!