质因数分解

GESP二级练习，多重循环，难度★✮☆☆☆。

luogu-B2084 质因数分解

题目要求

题目描述

已知正整数 $n$ 是两个不同的质数的乘积，试求出较大的那个质数。

输入格式

输入只有一行，包含一个正整数 $n$（$6<n<10^9$）。

输出格式

输出只有一行，包含一个正整数 $p$，即较大的那个质数。

样例输入 #1

21

样例输出 #1

7

题目分析

“最严谨且直白”的思路

首先，我们需要遍历所有可能的质因数，从$n-1$开始向下遍历，直到$i>=2$。对于每一个质因数$i$，我们需要检查$n$是否能被$i$整除，如果能，我们再计算出另一个质因数$j$，并且检查$i$和$j$是否都是质数。如果都是质数，我们就找到了较大的那个质数，输出即可。

“最科学”的思路

根据质数定理

每个大于 1 的正整数都可以唯一地分解为质数的乘积，忽略因子的顺序。

证明：

假设正整数 $n$ 可以由两个不同的质数相乘表示，并且存在两种不同的因式分解：

其中：

• $p, q, r, s$ 均为质数
• $p \neq q$ 且 $r \neq s$
• 假设 $p, q$ 与 $r, s$ 不是同一组数

由于 $n$ 是质数的乘积，根据唯一分解定理，质数的分解是唯一的。因此，如果 $p \times q$ 和 $r \times s$ 这两个乘积相等，则因子的集合必须相同。

首先，由于质数的定义，它们只能被 1 和自身整除。设 $p$ 是 $n$ 的一个质因子，这意味着：

由于 $p$ 是质数，根据质数的不可分性(欧几里得引理（Euclid’s Lemma）)，它只能整除其中一个因子，即 $p \mid r$ 或 $p \mid s$。但 $r$ 和 $s$ 也是质数，这意味着如果 $p \mid r$，则 $p = r$。类似地，$p \mid s$ 也意味着 $p = s$。

因此，必须有 $p$ 等于 $r$ 或 $s$，同理 $q$ 也必须等于另一个质数。这样我们得到：

这表明假设的两个分解实际上是相同的，只是顺序不同。

因此，我们只需要从小到大遍历找到第一个因数，然后输出 $n \div i$的结果即可。

{% include custom/custom-post-content-inner.html %}

示例代码

代码一：“最严谨且直白”的思路

#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;
int main() {
    int n; // 定义变量n
    cin >> n; // 读取输入的n
    for (int i = n - 1; i >= 2; i--) { // 从n-1开始向下遍历，直到i>=2
        if (n % i == 0) { // 如果n能被i整除
            int j = n / i; // 计算n/i的商
            bool flag = true; // 初始化标志为真
            for (int k = 2; k <= sqrt(i); k++) { // 从2开始遍历到i的平方根
                if ((i % k == 0 && i != k) || (j % k == 0 && j != k)) { // 如果i或j能被k整除，但不是k本身
                    flag = false; // 标志为假
                    break; // 跳出循环
                }
            }
            if (flag) { // 如果标志为真
                cout << i; // 输出i
                break; // 跳出循环
            }
        }
    }
    return 0;
}

代码二：“最科学”的思路

#include <iostream>

using namespace std;
int main() {
    int n; // 定义变量n
    cin >> n; // 读取输入的n
    for (int i = 2; i <= n - 1; i++) { // 从2开始遍历到n-1
        if (n % i == 0) { // 如果n能被i整除
            cout << n / i; // 输出n/i的商
            break; // 跳出循环
        }
    }
    return 0;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号