一起数质数-爱代码爱编程
质数是指在大于1的自然数中,除了1和它本身以外不再有其它因数的自然数。
也就是大于1的自然数中只能被1和它本身整除的数为质数(因数个数为2)
则有质数a(a>=2)只能被1或a整除,不能被2~a-1中的任意一数整除(a==2除外)
不能被整除也就是求余运算不能为0,也就是a%(2~a-1)!=0
for(i=2;i<=a-1;i++) a%i!=0
我们想一下我们判断一个数为质数分为几步
- 第一步:得到要进行判断的数a
- 第二步:用a除以2~a-1中的每一个数
- 第三步:判断2~a-1中有没有能整除的
- 第四步:得到结果
我们将上面这个过程转化为c语言的实现过程
- 第一步:输入存储a的值(因为我们是数质数,所以,让a从2开始,自加至正无穷)
- 第二步:存储b的值(这里的b也就是2~a-1,也就是让b从2开始,自加至a-1)
- 第三步:a%b
- 第四步:将a%b==0的次数存储在count中
- 第五步:判断count数是否0,为0是质数,
- 第六步:输出结果
我们审视这六步发现只是两个简单的循环而已
就像我们审视判断质数的式子发现它只有两个变量(a、b)一样
a%b //变量a,变量b
流程图如下
质数是无穷的,这个流程图永远不会结束
完整代码如下
#include <stdio.h>
#include <stdlib.h>
int main()
{
int a=2, b, count=0;
while (1)
{
b = 2;
while (b < a)//(等价于b<=a-1)
{
if (a % b == 0)
{
count++;
break;
}
b++;
}
if (count == 0)
printf("%d\t", a);
count = 0;
a++;
}
return 0;
}
while(1) 代表无限执行 条件表达式只写一个常数的情况下代表恒成立(0除外,为0直接判不成立)
我们将条件表达式改为a<=100,就可以打印100以内的质数
a<=100
a<=1000
a<=10000