当前位置：首页 > news >正文

完全数和质数算法详解

news 来源：原创 2025/5/9 14:30:03

完全数是指一个正整数，它等于其所有真约数（即除了自身以外的所有正因数）之和。例如，6 是一个完全数，因为它的真约数是 1、2 和 3，且 1 + 2 + 3 = 6。

1 计算约数和

1.1 遍历

遍历其所有可能的约数并计算它们的和。如果和等于该数，则为完全数，否则不是。

#include <iostream>
using namespace std;int main() {int N;cin >> N;while (N--) {int X;cin >> X;int sum = 0;for (int i = 1; i * i <= X; ++i) {if (X % i == 0) {if (i != X) sum += i; int j = X / i;if (j != X && j != i) sum += j; }}cout << X << (sum == X ? " is" : " is not") << endl;}return 0;
}

1.2 生成表

#include <iostream>
#include <vector>
using namespace std;int main() {int N;cin >> N;vector<int> perfect = {6, 28, 496, 8128, 33550336}; while (N--) {int X;cin >> X;bool isPerfect = false;for (int num : perfect) {if (num == X) {isPerfect = true;break;}}cout << X << (isPerfect ? " is" : " is not") << endl;}return 0;
}

2 判断质数

2.1 错误解法遍历

#include <iostream>
using namespace std;int main() {int n;cin >> n;for (int j = 1; j <= n; j++) {int x;bool is_prime = true;cin >> x;if (x == 1) cout << x << " is not" << endl;else {int i;for (i = 2; i < x; i++) {if (x % i == 0) {is_prime = false;break;} else is_prime = true;}if (is_prime) cout << x << " is" << endl;else cout << x << " is not" << endl;}}return 0;
}

时间复杂度：对于每个输入的数字 $x$ ，内层循环从 $2$ 到 $x - 1$ 遍历，因此单次判定的时间复杂度为 $O (x)$ 。如果需要判断 $N$ 个数字，则总时间复杂度为 $\cdot X)$ ，其中 $X$ 是输入数字的最大值。当 $X$ 较大（例如 $10^9$ ）时，通常会TLE

2.2 正确解法

根据数学原理，一个数 $x$ 如果不是质数，那么它一定可以分解为两个因数 $a$ 和 $b$ ，且至少有一个因数小于等于 $\sqrt{x}$ 。因此，我们只需要检查从 $2$ 到 $\sqrt{x}$ 的所有整数即可。

#include <iostream>
using namespace std;int main() {int n;cin >> n;while (n--) {int x;bool is_prime = true;cin >> x;if (x == 1) cout << x << " is not " << endl;else {int i;for (i = 2; i <= x / i; i++) {if (x % i == 0) {is_prime = false;break;}}if (is_prime) cout << x << " is " << endl;else cout << x << " is not " << endl;}}return 0;
}

时间复杂度： 对于每个数字 $x$ ，只需检查从 $2$ 到 $\sqrt{x}$ 的所有整数，因此单次判定的时间复杂度为 $O(\sqrt{x})$ 。如果需要判断 $N$ 个数字，则总时间复杂度为 $\cdot \sqrt{X})$ ，其中 $X$ 是输入数字的最大值。

为什么只需要检查到 $\sqrt{x}$

如果一个数 $x$ 不是质数，那么它一定可以分解为两个因数 $a$ 和 $b$ ，且至少有一个因数小于或等于 $\sqrt{x}$ 。

一个数 $x$ 是合数（非质数），意味着它可以被分解为两个整数的乘积： $x=a\cdot b$ ，其中 $a$ 和 $b$ 都是大于1的整数。如果 $x$ 是质数，则它无法被任何小于 $x$ 的正整数整除（除了1和自身）。

假设 $x$ 是一个合数，那么它可以写成两个因数的乘积：
$x=a\cdot b$
其中 $a$ 和 $b$ 都是正整数，且 $a\leq b$ （为了简化讨论，我们可以假设 $a$ 是较小的那个因数）。
$a\cdot b=x\implies a\leq\sqrt{x}\quad\text{或}\quad b\leq\sqrt{x}$

因为如果 $a>\sqrt{x}$ 且 $b>\sqrt{x}$ ，那么 $a\cdot b>\sqrt{x}\cdot\sqrt{x}=x$ ，这与 $a\cdot b=x$ 矛盾。因此，至少有一个因数 $a$ 或 $b$ 满足 $a\leq\sqrt{x}$ 或 $b\leq\sqrt{x}$ 。换句话说，如果 $x$ 是合数，那么它一定存在一个小于或等于 $\sqrt{x}$ 的因数。

反证法：

如果 $x$ 是合数，则它一定存在一个小于或等于 $\sqrt{x}$ 的因数。

证明：

假设 $x$ 是合数，且 $x$ 的所有因数都大于 $\sqrt{x}$ 。
设 $x=a\cdot b$ ，其中 $a$ 和 $b$ 都是大于 $\sqrt{x}$ 的整数。
根据假设， $a>\sqrt{x}$ 且 $b>\sqrt{x}$ 。
因此， $a\cdot b>\sqrt{x}\cdot\sqrt{x}=x$ ，这与 $x=a\cdot b$ 矛盾。
故假设不成立，即 $x$ 至少存在一个小于或等于 $\sqrt{x}$ 的因数。

示例分析：

正例： $x = 36$

$36=6\cdot6$ ，其中 $6=\sqrt{36}$ 。所有因数对为 $(1, 36), (2, 18), (3, 12), (4, 9), (6, 6)$ 。只需要检查 $2, 3, 4, 5, 6$ 即可找到因数。

反例： $x = 73$

$73$ 是质数，无法分解为两个整数的乘积。检查 $2, 3, 4, 5, 6, 7, 8$ 后发现 $73$ 无法被整除。