证明: 假设 \(\exists{n}\in\mathbb{R},n\) 有两个大于 \(\sqrt{n}\) 的质因子, 分别记为 \(p_1,p_2\),
??? 则 \(n\geqslant p_1p_2\),
??? 又 \(p_1,p_2>\sqrt{n}\),
???\(\therefore p_1p_2>n\), 矛盾,
???\(\therefore\) 一个数最多只有一个大于 \(\sqrt{n}\) 的质因子.
?? 所以我们只需要考虑 \(1~\sqrt{n}\) 之间的质因子, 用他们来试除 \(n\), 若最终 \(n\) 仍不为 \(1\), 那么此时的 n 便是那个大于 \(\sqrt{n}\) 的质因子.
?? 试看下面这道例题.
例题: 小凯的函数
?? 很显然, 这一题就是要我们求出一个数的质因子个数.
- up=sqrt(a);
- ans=0;
- //prime[] 数组是用欧拉筛预处理出的质数
- for(int i=1;prime[i]<=up;++i){
- while(a%prime[i]==0){
- a/=prime[i];
- ans++;
- }
- }
- if(a!=1) ans++;
?? 这样写看起来没有任何问题, 然而提交之后你就会发现这样会超时, 只能得到 50 分.
?? 那么, 问题出在哪里?
?? 前面我们已经知道, 一个数最多只有一个大于 \(\sqrt{n}\) 的质因子, 所以我们只需要考虑 \(1~\sqrt{n}\) 之间的质因子. 而每次试除成功后,\(a\) 的值已然发生改变 (为了方便叙述, 我们将之记作 \(a'\)). 我们在接下来的试除过程中, 只需考虑 \(1~\sqrt{a'}\) 的质因子,\(\sqrt{a'}~\sqrt{a}\) 的质因子就不用再考虑了. 而如果我们按照上述写法, 则仍然考虑了 \(\sqrt{a'}~\sqrt{a}\) 这一部分质因子, 引起超时. 所以我们应当在每次 \(a\) 的值发生改变后, 就相应地改变上界, 减少时间的浪费. 虽然这样时间复杂度仍然是 \(O(\sqrt{n})\) 级别的, 但是由于减少了冗余的试除, 实际跑起来会快许多.
?? 代码如下.
- up=sqrt(a);
- for(register int i=1;prime[i]<=up;++i){
- if(a%prime[i]==0){
- while(a%prime[i]==0){
- a/=prime[i];
- ++ans;
- }
- up=sqrt(a);
- }
- }
- if(a!=1) ++ans;
质因数分解
来源: http://www.bubuko.com/infodetail-3394288.html