完全数、统计质数个数问题中 代码的优化问题
2022/1/6 23:03:26
本文主要是介绍完全数、统计质数个数问题中 代码的优化问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
在我们初次做完全数 问题时 有可能会遇到TLE(时间超限)的情况,因此写这篇文章来深入分析一下 并且 提出良好的解决方案。
完全数问题如下:
一个整数,除了本身以外的其他所有约数的和如果等于该数,那么我们就称这个整数为完全数。
例如,6 就是一个完全数,因为它的除了本身以外的其他约数的和为 1+2+3=6。
现在,给定你 N 个整数,请你依次判断这些数是否是完全数。
输入格式
第一行包含整数 N,表示共有 N 个测试用例。
接下来 N 行,每行包含一个需要你进行判断的整数 X。
输出格式
每个测试用例输出一个结果,每个结果占一行。
如果测试数据是完全数,则输出 X is perfect
,其中 XX 是测试数据。
如果测试数据不是完全数,则输出 X is not perfect
,其中 XX 是测试数据。
数据范围
1 ≤ N ≤ 100
1 ≤ X ≤ 10^8
输入样例
3 6 5 28
输出样例:
6 is perfect 5 is not perfect 28 is perfect
先给出普通写法,也就是大多数同学的写法:
#include<cstdio> #include<iostream> using namespace std; int main() { int n, x, i, sum; cin >> n; while (n) { sum = 0; cin >> x; for (i = 1; i < x; i++) { if (x % i == 0) sum += i; } if (sum == x) printf("%d is perfect\n", x); else printf("%d is not perfect\n", x); n--; } return 0; }
当提交的时候,会发现时间超限!这是为什么呢?接下来分析一下:
C++写代码时,每秒钟会计算1e8次 也就是一亿次,如果n = 100, x = 10^8,那么总共会计算100亿次,远远超过了 时间限制,如何对代码进行优化呢?
首先,假设 d是x的约数,那么x / d也是x的约数。例如2是12的约数,而12 / 2 = 6 也是12的约数,所以只用枚举小的那个约数就可以减少运算量了。即d <= x / d 即d * d <= x 即 d <= 根号 x 。
代码实现
#include<cstdio> #include<iostream> using namespace std; int main() { int n, x, i, sum; cin >> n; while (n--) { sum = 0; cin >> x; for (i = 1; i * i <= x; i++) { if (x % i == 0) { if (i < x) sum += i; if (i != x / i && x / i < x) sum += x/i; } } if (sum == x) printf("%d is perfect\n", x); else printf("%d is not perfect\n", x); } return 0; }
另作说明:1.for语句里面 每一个 if 语句 都要判断 i < x ,这是为了避免 读入x = 1时 输出 1 is perfect 的情况。 2.第二个if 中 i != x / i 是为了 避免 当x 为36时(约数为 6 和 6)重复加上6的情况。
还有一道经典的统计素数个数的问题 也用到了这个优化方式:
题目
一个大于 1 的自然数,如果除了 1 和它自身外,不能被其他自然数整除则称该数为质数。
例如 7 就是一个质数,因为它只能被 1 和7 整除。
现在,给定你 N 个大于 1 的自然数,请你依次判断这些数是否是质数。
输入格式
第一行包含整数 N,表示共有 N个测试数据。
接下来 N 行,每行包含一个自然数 X。
输出格式
每个测试用例输出一个结果,每个结果占一行。
如果测试数据是质数,则输出 X is prime
,其中 XX 是测试数据。
如果测试数据不是质数,则输出 X is not prime
,其中 XX 是测试数据。
数据范围
1 ≤ N ≤ 100,
1 < X ≤ 10^7
#include<cstdio> #include<iostream> using namespace std; int main() { int n, x, i; bool is_prime = true; cin >> n; while (n--) { cin >> x; is_prime = true; for (i = 2; i * i <= x; i++) { if (x % i == 0) { is_prime = false; break; } } if (is_prime == true) printf("%d is prime\n", x); else printf("%d is not prime\n", x); } return 0; }
这篇关于完全数、统计质数个数问题中 代码的优化问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23线下车企门店如何实现线上线下融合?
- 2024-12-23鸿蒙Next ArkTS编程规范总结
- 2024-12-23物流团队冬至高效运转,哪款办公软件可助力风险评估?
- 2024-12-23优化库存,提升效率:医药企业如何借助看板软件实现仓库智能化
- 2024-12-23项目管理零负担!轻量化看板工具如何助力团队协作
- 2024-12-23电商活动复盘,为何是团队成长的核心环节?
- 2024-12-23鸿蒙Next ArkTS高性能编程实战
- 2024-12-23数据驱动:电商复盘从基础到进阶!
- 2024-12-23从数据到客户:跨境电商如何通过销售跟踪工具提升营销精准度?
- 2024-12-23汽车4S店运营效率提升的核心工具