一个大合数的质因子分解怎么做到nln(n)复杂度解决啊

Question

一个大合数的质因子分解怎么做到nln(n)复杂度解决啊，最近导师要求对一个网络数据进行加密，需要这方面的知识。

Answer 1

这个啊，首先你知道一个合数n的质因子不可能出现两个质因子p,q都大于sqrt(n)吧！ 所以你可以预先处理出sqrt(n)内的所有素数，这个复杂度是sqrt(n)的，可以用线性筛。然后你顺便统计下每一个数的最大质因子，这个可以在nlogn解决。这就是普通的素数筛法的。然后对于合数n，除以他的最大质因子，变为n',重复这个过程，这个复杂度是nlnn的。希望对你有帮助。