背景：
有时分解一个很大的合数，因为可能质因子很大，导致分解时复杂度不是严格O(log2n)，需要用一点技巧使其复杂度得到保证。
做法：
在筛法求质数时，不用把质数存储成一张表，而用一个数组big[i]保存每个数（不管是质数还是合数）的最大质因数，接着在分解一个数x时，令y=x，之后不断地y/=big[y]，并且把每次的big[y]作为x的一个质因数，这样就可以了。
20161115
本文共 247 字，大约阅读时间需要 1 分钟。
背景：
有时分解一个很大的合数，因为可能质因子很大，导致分解时复杂度不是严格O(log2n)，需要用一点技巧使其复杂度得到保证。
做法：
在筛法求质数时，不用把质数存储成一张表，而用一个数组big[i]保存每个数（不管是质数还是合数）的最大质因数，接着在分解一个数x时，令y=x，之后不断地y/=big[y]，并且把每次的big[y]作为x的一个质因数，这样就可以了。
20161115
转载于:https://www.cnblogs.com/YuanZiming/p/6067521.html