如何用python快速分解素因数

sikro

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

ymhld

递归也很快吧

kesai

以前的代码，自己看吧，nodejs的版本

[JavaScript] 纯文本查看 复制代码

//ref:https://www.geeksforgeeks.org/find-largest-prime-factor-number/

/**
 * 查找最大因子
 * [url=home.php?mod=space&uid=952169]@Param[/url] {*} 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[2] = counts[2] ? counts[2] + 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[i] = count;
        }
    }
    if (x > 2) counts[x] = 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

python本身就太慢了