【题目来源】
【题目描述】
已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。
【输入格式】
输入一个正整数 n。
【输出格式】
输出一个正整数 p，即较大的那个质数。
【输入样例】
21
【输出样例】
7
【数据范围】
1≤n≤2×10^9
【算法分析】
● 整数唯一分解定理（算术基本定理）
任何一个大于 1 的正整数 n，都可以唯一地表示成有限个质数的乘积形式：n=p₁ᵏ¹×p₂ᵏ²×...×pₘᵏᵐ，其中 p₁<p₂<...<pₘ 是质数，k₁，k₂，....，kₘ 是正整数.且这种分解方式在不考虑顺序的情况下是唯一的。
● 欧拉函数性质
欧拉函数 φ(n) 是数论中的重要函数，用于计算 1~n 中与 n 互质的正整数的个数。特别地，当 n=1 时，φ(1)=1。
（1）若 p 是质数，φ(p)=p-1。
例如，φ(5)=5-1=4（表示 1~5 中与 5 互质的正整数有 1,2,3,4 等 4 个）。
（2）若 n=pᵏ，φ(pᵏ)=pᵏ-pᵏ⁻¹。
例如，φ(8)=2³-2²=8-4=4（表示 1~8 中与 8 互质的正整数有 1,3,5,7 等 4 个）
（3）积性函数：当 a,b 互质时，φ(ab)=φ(a)φ(b)。
例如，φ(10)=φ(2)×φ(5)=1×4=4（表示 1~10 中与 10 互质的正整数有 1,3,7,9 等 4 个）
（4）通用计算公式：φ(n)=n×(1-1/p₁)×(1-1/p₂)×...×(1-1/pₘ)。其中，p₁，…，pₘ，是 n 的所有质因数。
例如， 由于 18=2×3²，所以 φ(18)=18×(1-1/2)×(1-1/3)=6（表示 1~18 中与 18 互质的正整数有 1,5,7,11,13,17 等 6 个）。
● 基于整数唯一分解定理，求整数 n 的不同质因子的个数：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;void cal(LL n) {LL cnt=0;for(LL i=2; i*i<=n; i++) {if(n%i==0) {cnt++;while(n%i==0) n/=i;}}if(n>1) cnt++;cout<<cnt;
}int main() {LL x;cin>>x;cal(x);return 0;
}/*
in:18
out:2
*/
● 利用基于整数唯一分解定理的欧拉函数，求 1~n 中与 n 互质的正整数的个数：
#include <bits/stdc++.h>
using namespace std;typedef long long LL;void cal(LL n) {LL cnt=n;for(LL i=2; i*i<=n; i++) {if(n%i==0) {cnt=cnt/i*(i-1);while(n%i==0) n/=i;}}if(n>1) cnt=cnt/n*(n-1);cout<<cnt;
}int main() {LL x;cin>>x;cal(x);return 0;
}/*
in:18
out:6
*/【算法代码】
#include <bits/stdc++.h>
using namespace std;int main() {int n;cin>>n;for(int i=2; i*i<=n; i++) {if(n%i==0) {cout<<n/i;break;}}return 0;
}/*
in:21
out:7
*/
【参考文献】