网站 › 『编程语言讨论求助区』 › 如何用python快速分解素因数

sikro 发表于 2021-2-22 22:20

如何用python快速分解素因数

有没有算法可以快速计算出一个合数的因数，由于数字特别大(几千位)，不能用递归方式求解，有没有快速的算法？

ymhld 发表于 2021-2-22 22:36

递归也很快吧

kesai 发表于 2021-2-22 22:50

本帖最后由 kesai 于 2021-2-22 22:51 编辑

以前的代码，自己看吧，nodejs的版本
//ref:https://www.geeksforgeeks.org/find-largest-prime-factor-number/

/**
* 查找最大因子
* @Param {*} x
*/
function get_max_factor(x) {
    var maxPrime = -1;
    while (x % 2 === 0) {
      x /= 2;
      maxPrime = 2;
    }
    for (var i = 3; i < Math.sqrt(x) + 1; i += 2) {
      while (x % i === 0) {
            x /= i;
            maxPrime = i
      }
    }
    if (x > 2) return x;
    return maxPrime;
}
/**
* 分解因子并返回各个因子组成个数
* @param {} x
*/
function get_factors(x) {
    var counts = {};
    while (x % 2 === 0) {
      x /= 2;
      counts = counts ? counts + 1 : 1;
    }
    for (var i = 3; i < Math.sqrt(x) + 1; i += 2) {
      if (x % i === 0) {
            var count = 0;
            while (x % i === 0) {
                x /= i;
                count++;
            }
            counts = count;
      }
    }
    if (x > 2) counts = 1;
    return counts;
}

/**
* 大数的分解,以数组形式返回因子组成
* @param {*} n
*/
function factorize(n) {
    var res = []
    while (!(n % 2 > 0)) {
      n /= 2;
      res.push(2);
    }
    for (i = 3; i <= Math.sqrt(n); i += 2) {
      while (n % i == 0) {
            res.push(i);
            n = n / i;
      }
    }
    if (n > 2) {
      res.push(n);
    }
    return res;
}

Ldfd 发表于 2021-2-23 09:07

python本身就太慢了

查看完整版本: 如何用python快速分解素因数