完全数、统计质数个数问题中 代码的优化问题

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

上一篇:ICPC2021 沈阳 L - Perfect Matchings 树上背包 + 容斥


下一篇:2组-Alpha冲刺-3/6