频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
用C语言打印100~200之间的素数的操作分享
2018-05-14 14:32:13      个评论    来源:Pin_na  
收藏   我要投稿

这是一道较为基础的题目,那么我们先来复习了解一下素数的概念——素数又称质数,是指一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数;否则称之为合数。

那么根据定义我们很容易想到一种方法,就是依次列出100~200间所有的数,用它去除以2 ~( i - 1)的所有数,若均不能整除,则为素数。

#define _CRT_SECURE_NO_WARNINGS 1
#include 
int main()
{
	int i = 0;
	int j = 0;
	int count = 0;//定义计数器
	for (i = 100; i <= 200; i++)
	{
		for (j = 2; j <= i - 1; j++)
		{
			if (i%j == 0)//判断是否整除
			{
				break;//整除则不是素数,跳出循环开始验证下一个数
			}
		}
		if (i == j)//仅能被自身整除
		{
			printf("%d ", i);
			count++;
		}
	}
	printf("\n");
	printf("count=%d\n", count);
	system("pause");
	return 0;
}

上面这种方法需要程序对每个数字进行逐个比较运算,执行速度较慢,以为整数i不能被比i/2大的数所整除,所以我们可以对代码进行优化:

#define _CRT_SECURE_NO_WARNINGS 1
#include 
int main()
{
	int i = 0;
	int j = 0;
	int n = 0;
	int count = 0;
	for (i = 100; i <= 200; i++)
	{
		n = i / 2;//储存i/2用来比较
		for (j = 2; j <= n; j++)
		{
			if (i%j == 0)
			{
				break;
			}
		}
		if (j > n)
		{
			printf("%d ", i);
			count++;
		}
	}
	printf("\n");
	printf("count=%d\n", count);
	system("pause");
	return 0;
}

这样一来,程序运行速度就会提高,但是其实这段代码还可以进一步优化。同样的道理,用i的平方根会更加优化这种算法,我们在这里需要引用头文件math.h中的平方根函数sqrt()来实现:

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
int main()
{
	int i = 0;
	int j = 0;
	int n = 0;
	int count = 0;
	for (i = 100; i <= 200; i++)
	{
		n = sqrt(i);//储存i的平方根用来比较
		for (j = 2; j <= n; j++)
		{
			if (i%j == 0)
			{
				break;
			}
		}
		if (j > n)
		{
			printf("%d ", i);
			count++;
		}
	}
	printf("\n");
	printf("count=%d\n", count);
	system("pause");
	return 0;
}

那么现在程序执行的速度已经大大提高了,但是我们稍作思考就会发现,其实这段代码还可以做一步优化,因为大家都知道所有的偶数都不是素数,所以我们让i从101开始,每次循环时对其+2,就可以使程序减少一半的运算量:

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
int main()
{
	int i = 0;
	int j = 0;
	int n = 0;
	int count = 0;
	for (i = 101; i <= 200; i += 2)//i从101开始,每次循环时+2
	{
		n = sqrt(i);
		for (j = 2; j <= n; j++)
		{
			if (i%j == 0)
			{
				break;
			}
		}
		if (j > n)
		{
			printf("%d ", i);
			count++;
		}
	}
	printf("\n");
	printf("count=%d\n", count);
	system("pause");
	return 0;
}

最后为大家附上程序运行的结果:

\

点击复制链接 与好友分享!回本站首页
上一篇:C程序计时方法实现教程
下一篇:C语言基础学习之指针,数组和内存杂讲
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站