(O(根号n))分解质因数
1 分解质因数模板
1.1 暴力做法  -  -  试除法
1.1.1 思想:
1.1.2 时间复杂度
1.1.3 板子
1.2 进阶版
分解质因数模板
暴力做法  -  -  试除法
我遇到一个质因数,就把它能整除掉的所有后面的数都给整除掉.可能容易不理解的地方在于:我们会不会找到合数没有被小于它的质因数整除掉?
答:不会的.因为我们是从小到大进行枚举因数i,遇到可以整除的就把该因数i的所有因数都除掉了,后面不会找出一个合数了.即当我枚举到i时就意味着我已经把从0~i-1的因子都除干净了,那么当n%i 0, 且0~i-1中没有一个是i的因子,那么i就是一个质数,i就为n的质因子
O(logn)
板子
v