算法一
根据唯一分解定理，小于 \(n\) 的最大的能整除 \(n\) 的整数一定就是答案，可以暴力枚举。
时间复杂度 \(O(n)\)，实际得分 \(60\)。
算法二
发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。
而较小的那个质数一定小于等于 \(\sqrt n\)，我们枚举它即可。
时间复杂度 \(O(\sqrt n)\)，实际得分 \(100\)。
P1075 [NOIP2012 普及组] 质因数分解
发布时间 2023-09-21 23:03:21作者: 御坂夏铃
根据唯一分解定理，小于 \(n\) 的最大的能整除 \(n\) 的整数一定就是答案，可以暴力枚举。
时间复杂度 \(O(n)\)，实际得分 \(60\)。
发现算法一不能通过的原因是较大的那个质数可能的取值范围太大了。
而较小的那个质数一定小于等于 \(\sqrt n\)，我们枚举它即可。
时间复杂度 \(O(\sqrt n)\)，实际得分 \(100\)。