题解 | #质数因子#
质数因子
https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
很容易就会超时，通过下面的例子来试图理解大神们的想法
以例子来理解:
有一个数N,以及她的平方根 /N
N/a==b -> a为除数，b为商,，当a、b相等时，有a*a=N；此时平方根即为其因数
则以其平方根为界限，若 N%a==0 && a<sqrt(N)则其另一个因数b必然有： b>sqrt(N) && N%b==0
同时 b=N/a 则 N%(N/a)==0 -> N/(N/a)==c -> c==a ....
通过上面的分析就可以分析出：a最小的时候就是2，最大的时候就是 a==b == sqrt(N)，那么就不再需要判断大于平方根的情况，a大于平方根时的计算就是多余的
b最小的时候就是 b==a == sqrt(N)
在循环中a越来越大，越来越逼近算术平方根，到达极限时，这个a就是最接近平方根的数，每次运算都会改变N的值，N此时的值其实就是各次运算的b，
b也在越来越向左逼近平方根，当a极限时，我们将a存储上了，但别忘了，各个a的累乘并不等于N，因为你忘了把最靠左的那个b乘进去
原因： N/a1=b1 b1/a2=b2 ... -> N==a1*b1==a1*a2*b2
a2、b2两个都是已经极限逼近最后一次平方根（一共平方根了n次）的数
那么问题来咧：为什么a1、a2、a3、a... 以及 bn 是质数呢？？？明明在循环中的 an 都是自增加一。
难怪大神在每次循环++之前要在if语句中自减1，这样就能保证一堆质数的累乘。
N / 2*2*2*2... 除不尽时，它必然不再会被2整除，此时除数不可能为2的倍数，再往下，假如设S为商
S / 3*3*3*3... 除不尽时，它必然不再会被3整除，此时除数不可能为3的倍数
S / 5*5*5*5... 除不尽时，它必然不再会被5整除，此时除数不可能为5的倍数
飞鱼科技公司福利 177人发布
查看9道真题和解析