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

【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 <stdio.h>
#include <math.h>
//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;
}

最后

以上就是鲤鱼柚子为你收集整理的【C语言】输出范围内所有素数时，时间复杂度优化问题的全部内容，希望文章能够帮你解决【C语言】输出范围内所有素数时，时间复杂度优化问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。