【C语言】输出范围内所有素数时，时间复杂度优化问题

素数：只能被1和它本身整除的数，也叫 质数

要输出范围内所有的质数，首先要给定范围，例：100 ~ 200 之间
由此，一般最外层循环条件为：

for(i = 100; i < 201; i++)

但是，偶数不可能是质数，所以可以进行第一次优化：

for(i = 101; i < 201; i += 2)				//i += 2  == i = i + 2
//由 奇数 加 2的方式 排除范围内所有偶数 

接下来判断 i 是否为素数，需用 i % 1 ~ i 之间的所有数：

int flag = 1;			//由标志变量 flag 是否为1 判断 i 是否为素数
for (n = 2; n < i; n++)			//2 ~ i-1
{
	if (i % n == 0)		//判断 i 是否可被其他数 整除
	{
		flag = 0;	//标志变量改变
		break;
	}
}	
if (flag == 1)		//若没被整除 则标志变量不改变 flag == 1   则 i 为素数 输出
{
	printf("%5d", i);
}

但是 ， 如果一个数可以被另一个数整除 那么这个数就可以写成两数相乘的形式
例：195 == 1 *195 == 3 * 65 == 5 * 39 == 13 * 15
以 两数相乘 的形式 表示，则其中至少一个数 <= 这个数开平方
因为 一个数的平方根 是 此数约数（先这么看）的中位数
若还有其他约数 则一对约数 其中一数 一定小于这个数的平方根 对应的另一个约数 一定大于这个数的平方根
即 只要在 1 ~ 平方根 范围内 不能被整除 则 在 平方根 ~ 本身 范围内 也不可能被整除
所以，可以优化素数判断：

for (n = 2; n < sqrt(i); n++)			//sqrt() 开平方函数  在 math.h 库内
	{
		if (i % n == 0)
		{
			flag = 0;
			break;
		}
	}
	if (flag == 1)
	{
		printf("%5d", i);
		count++;
	}

OK 代码简单优化结束；
下面是 整个程序代码

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
//100 ~ 200 之间的素数

int main()
{
	int n = 0;
	int i = 0;
	int count = 0;
	printf(" 100 ~ 200 之间的素数有：n");
	
	for (i = 101; i < 201; i += 2)		//偶数不可能为素数 则 从奇数开始判断且  +=2
	{
		int flag = 1;
		//for (n = 2; n < i; n++)		//此 试 除  非最优
		//{
		//	if (i % n == 0)
		//	{
		//		flag = 0;
		//		break;
		//	}
		//}		
		for (n = 2; n < sqrt(i); n++)			
		{
			if (i % n == 0)
			{
				flag = 0;
				break;
			}
		}
		if (flag == 1)
		{
			printf("%5d", i);
			count++;
			if (count % 5 == 0)			//利用 计数变量 每输出5个素数 换行
				printf("n");
		}
	}

	return 0;
}