在我们初次做完全数 问题时 有可能会遇到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; }