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

完全数和质数算法详解

article 2025/2/24 23:06:46

完全数是指一个正整数，它等于其所有真约数（即除了自身以外的所有正因数）之和。例如，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}$ 的因数。