完全数和质数算法详解

完全数是指一个正整数，它等于其所有真约数（即除了自身以外的所有正因数）之和。例如，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$ 个数字，则总时间复杂度为 $O(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$ 个数字，则总时间复杂度为 $O(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\le b$（为了简化讨论，我们可以假设$a$是较小的那个因数）。
$$a\cdot b=x⟹a\le \sqrt{x}\text{或}b\le \sqrt{x}$$

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

---

反证法：

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

证明：

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

---

示例分析：

正例：$x=36$

$36=6\cdot 6$，其中$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$无法被整除。