C语言判断素数及输出100-200间素数实战

C语言素数判断逻辑与实现

素数（又称质数）是指大于1的自然数中，除了1和它本身以外不再有其他因数的数。在编程实践中，判断一个数是否为素数是入门算法的经典案例。以下介绍两种常用方法，并附带完整代码示例。

第1步：采用穷举法判断素数

目的： 通过从2遍历到 n-1，验证是否存在因子，适用于理解基础循环逻辑。

• 入口： 控制台输入正整数 n。
• 动作： 使用 for 循环从 i=2 遍历至 n-1。若 n % i == 0，说明存在因子，立即跳出循环（break）。
• 关键参数： 循环变量 i 和输入值 n。
• 完成状态： 循环结束后，检查 i 是否小于 n。若是，则非素数；否则为素数。

代码实现如下：

#include <stdio.h>
 
void main()
{
	int i,n;
	printf("请输入一个正整数：");
	scanf("%d",&n);
	for(i=2;i<=n-1;i++)
	{
		if(n%i==0) break;
	}
		if(i<n)
		printf("%d不是素数\n",n);
		else 
			printf("%d是素数\n",n);
}

第2步：优化算法至根号n判断

目的： 减少计算量。数学原理表明，若 n 有因子，必有一个小于等于 √n。因此只需遍历至 k = √n 即可。

• 入口： 引入头文件 <math.h> 以使用平方根函数。
• 动作： 计算 k = sqrt(n)，循环条件改为 i <= k。
• 重要参数： 需声明整型变量 k 存储平方根结果。
• 完成状态： 若循环结束时 i <= k，说明在范围内找到了因子，为非素数；反之则为素数。

优化后的代码实现：

#include <stdio.h>
#include <math.h> /*调用数学函数需要命名此头文件*/
void main()
{
	int i,n,k;
	printf("请输入一个正整数：");
	scanf("%d",&n);
	k=sqrt(n);/*调用一个根号函数*/
	for(i=2;i<=k;i++)
	{
		if(n%i==0) break;
	}
	if(i<=k) printf("%d不是素数\n",n);
	else printf("%d是素数\n",n);
}

实战：输出100~200之间的所有素数

基于上述第二种高效方法，我们可以轻松扩展程序，筛选指定区间内的所有素数。该方法同样鼓励读者尝试第一种穷举法进行对比练习。

第3步：构建区间筛选循环

目的： 遍历特定范围内的每个数字，利用素数判断逻辑逐一输出符合条件的数。

• 入口： 外层循环控制目标数字 n，范围从 100 到 200。
• 动作： 对于每个 n，计算 k = sqrt(n)，内层循环判断是否有因子。
• 关键参数： 外层变量 n，内层判断变量 i 和阈值 k。
• 完成状态： 若内层循环自然结束且 i > k，打印当前 n。

完整实战代码如下：

#include <stdio.h>
#include <math.h>
 
void main()
{
	int i,n,k;
	for(n=100;n<=200;n++)
	{
		k=sqrt(n);
		for(i=2;i<=k;i++)
			if(n%i==0) break;
		if(i>k) printf("%d\n",n);
	}
}

以上就是C语言判断素数以及输出100-200之间素数的详细内容，更多关于C语言基础算法的资料请关注本站其它相关文章！