C语言求给定范围内的所有素数代码及解析

问题描述

求给定范围start〜end之间的所有素数。

问题分析

判定一个整数m是否为素数的关键就是要判定整数m能否被除1和它自身以外的任何其他整数所整除，若都不能整除，则m即为素数。

本题求的是给定范围start〜end之间的所有素数，考虑到程序的通用性，需要从键盘上输入start和end值，例如输入start=1，end=1000，则所编写的程序应能够打印出1〜1000之间的所有素数。

算法设计

由问题分析可知，该问题考虑用双层循环结构实现。

外层循环对start〜end之间的每个数进行迭代，逐一检查其是否为素数。外层循环的循环变量用变量m表示，m即代表当前需要进行判断的整数，显然其取值范围为start≤m≤end。

内层循环稍显复杂，完成的功能是判断当前的m是否为素数。设内循环变量为m，程序设计时i从2开始，直到为止。用i依次去除需要判定的整数m，如果m能够被中的任何一个整数所整除，则表示i必然小于或等于，则可以确定当前的整数m不是素数，因此，应提前结束该次循环。如果n不能被中的任何一个整数所整除，则在完成最后一次循环后，i还需要加1，即，之后才终止循环。此时，可以确定当前的整数m为素数。

可以使用标志位flag来监控内外循环执行的情况。在定义变量时将flag初值设为1，在内层循环中判断时，如果m能够被中的任何一个整数所整除，则在内循环中将flag设置为0。如果m不能被中的任何一个整数所整除，则在内循环中不会修改flag标志的值，退出内循环后它的值仍为1。此时在外循环中对flag的值进行判断，如果flag=0，则显然当前的m不是素数，如果flag=1，则当前的m是素数，应该将其打印出来。

还需要注意的是，在外循环中，每次要进行下一次迭代之前，要先将flag标志再次置为1。

程序流程图：

下面是完整的代码：

#include<stdio.h>

#include<math.h>

int main()

{

int start, end, i, k, m, flag=1, h=0;

do

{

printf("输入 起始数字 和 结束数字:");

scanf("%d%d", &start, &end);

}while(!(start>0 && start<end));

printf("......... (%d-%d)素数列表.........\n", start, end);

for(m=start; m<=end; m++)

{

k=sqrt(m);

for(i=2; i<=k; i++)

if(m%i==0)

{

flag=0;

break;

}

if(flag)

{

printf("%-4d",m);

h++;

if(h%10==0)

printf("\n");

}

flag=1;

}

printf("\n共有%d个素数\n", h);

return 0;

}

运行结果：

输入 起始数字 和 结束数字:1 200

......... (1-200)素数列表.........

1  2  3  5  7  11  13  17  19  23 

29  31  37  41  43  47  53  59  61  67 

71  73  79  83  89  97  101 103 107 109

113 127 131 137 139 149 151 157 163 167

173 179 181 191 193 197 199

共有47个素数

Linux公社的RSS地址 ： https://www.linuxidc.com/rssFeed.aspx

本文永久更新链接地址： https://www.linuxidc.com/Linux/2018-11/155472.htm