C语言解决素数判断问题（蓝桥杯）以及算法的优化

一、循环的嵌套

为了解决素数问题，我们就要涉及另一个问题了，循环的嵌套问题，前面学习了三种循环while，do while，for，这三种循环往往会嵌套在一起才能更好地解决问题，就是我们所说的：嵌套循环，这里我们就拿经典素数的判断来举例。

1.1 素数

//找出100~200之间的素数，并打印在屏幕上。 注：素数又称为质数，只能被1和本身整除的数字。（例如：7是质数，9就不是质数了，因为其除了能被1和本身被整除，还能被3整除）

1.2 题目解析

1. 要从100~~200之间找出素数，首先得产生100~200之间的数，这里可以使用循环解决，我这里使用for循环。
2. 每次产生一个数字，就得判断这个数字是不是素数。
3. 要判断i是否为素数，需要拿2~i-1之间的数字试除i，需要产生2到i-1之间的数字，也可以使用循环解决
4. 如果2到i-1之间有数字能整除i，则i不是素数，如果都不能整除，则i是素数

这里我给出两种写法，首先是第一种，我个人更偏向这种，更好理解。

大部分的代码解析都在图中注释里，这里就不作过多解释。当i等于101的时候，j等于2，内部循环开始，j从2到100依次与101试除，如果可以整除的时候，便不是素数，flag等于0，跳出break循环，不打印。如果不可以整除101，j变为3到100，依次与101试除，最后发现都不能整除，里面if的判断就不成立，程序走到外部的if（flag==1）;打印出101。后面i等于102重复上面的流程。这里break的作用是如果能提前找到一个j整除i，就能跳出内部循环，更快嘛，就比如说i是100，j等于2的时候就可以整除了，flag直接变为0了，就不用后面3到99依次与100试除了，节省步骤时间。而且可以看到，当flag=0的时候，就执行下一步break，跳出循环，不打印。

对这里还有疑惑的兄弟可以自行打开监视窗格，观察代码运行过程。

还有一些兄弟就要说了，这个flag我看着不舒服，不想要它，我这么写行不行？代码如下：

相信从代码的结果可以看出，这种写法是明显错误的。因为这里如果i=9，我们就拿9举例，因为方便。j=2，i%j不等于0呀，代码就走到else那里，直接打印了9的值，把它当作素数打印了，然而9除了1和本身，还可以被3整除，这样的逻辑直接没有考虑后续j等于3，4…之后的结果了，这下懂了错哪了吗？

这里我再给一种不需要flag，但是正确的代码形式：

在这里插入图片描述

我么们这里判断100是不是素数，for循环产生2-99的数字，这里发现2已经能够整除100了，说明100不是素数，break先跳出来，后面的3呀4呀一直到99呀都不用试除了，break就来到了//1。还有一种情况break没有被执行，当i等于101，就要用2到100的数字试除它，发现没有任何一个数字能够整除101，这里break就不执行了，当j等于101的时候，j<=i-1就不成立了就跳出来了，也会走到//1 2那里，这里就需要区分出来了，因为break满足跳到那里是 不是素数的情况，而j<i-1跳到那里是 是素数的情况，所以就有了外部循环printf这串代码。

但是我觉得这种方式不够方便好理解，我觉得还是用flag这种标量标记一下更好。 这种嵌套循环就是每次外部循环进来后，内层循环都要走一遍

二、算法优化

我们再在这里讲一下优化的版本。 在优化之前，我们先来思考，偶数有没有可能是奇数？没有可能。

在这里插入图片描述

这里我们就可以从101开始，每次+2,这样在奇数里面找素数是不是就更快了一些，我们这样写代码就在源头之上少了一半的数据，但最终的结果也是对的，这就是一层优化。

但是其实我们还可以再进行优化。 我们接下来展示这串代码，可能理解上有些难，小编尽量讲清楚一些。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//优化的版本
//sqrt 是开平方的函数
//需要的头文件是math.h
#include <math.h>
int main()
{
	int i = 0;
	//产生100~200之间的数字
	for (i = 101; i <= 200; i += 2) //少了一半的数据
	{
		int flag = 1;//假设这一次的i是素数
		//判断i是否是素数
		//是素数就打印
		//找出2~i-1之间的数字依次去试除i - for
		int j = 0;
		for (j = 2; j <= sqrt(i); j++)
		{
			if (i % j == 0)
			{
				flag = 0;//不是素数
				break;
			}
		}
		if (flag == 1)
			printf("%d ", i);
	}

	return 0;
}

使用sqrt（i）的原因就是，我们在试除的时候，压根没有必要试除那么多次的，我们在判断100是不是素数的时候使用的是2-99的数字去试除它的，实则没有比要，其实我们只要拿2-根号100这么多的数字去试除它就可以了，为什么呢？ 我们说假设有一个数字i，能够写成i=a*b的方式，a和b称为i的因子，那么a和b当中至少有一个数字是<=根号i的，为什么呢？如果是a>根号i，b>根号i，那么a×b的时候一定是大于i的，这下理解了吧。所以我们在根号i之前找到一个因子，要么是a要么是b，所以我们这里在2到根号i之间去找因子就对了，如果说在2到根号i之间都找不到因子的话，就找不到另一个数去整除i了，这样在之前试除100的时候，需要试除2-99之间的数字，需要试除98次，而改到2到根号100的时候，只需要试除9次就可以了，这样的提升是非常厉害的。

像蓝桥杯里面这种素数的判断就是经常使用的，算法竞赛嘛。

今天的内容就到这里了，别看字数少，小编想了好久的，始终感觉讲不清楚，希望大家能够看懂吧。