Problem
求 $[1 \dots N]$中素因子数最多且最小的数 $n$,$N$ 充分大。
Solution
将任意自然数 $n$ ($n>2$) 分解
$$ n = p_1^{k_1 } p_2^{k_2} p_3^{k_3} \dots P_m^{k_m} \quad (p_1<p_2< \dots <p_m)$$
则 $n$ 的因子数为 $$(k_1+1) (k_2+1) \dots (k_m+1)$$
假设 $[1 \dots N]$ ($N$ 充分大)中因子数最多且最小的数为 $n$,则显然可见下面两个结论
- $n$ 的素因子连续即 $ n=2^{k_1} 3^{k_2} 5^{k_3} \dots $
- $k1 \ge k2 \ge k3 \ge \dots \ge k_m$
由这两个必要条件,可以得到一个算法:DFS