时间戳

首页 > 解决方案 > Python：如何找到一个非常大的数的质因数？

python - Python：如何找到一个非常大的数的质因数？

问题描述

我的号码有 617 位数字。找到这个大数的质因数的最快方法是什么？

我的问题号码是19087688894909892783503691960213776632781962588843842839953893606139157282825376128877238229887486797933180624979637419997128020864299273315243907454874577263432419226852240380380880131843664800828228959920799327101817796594944161768692639537839544009100224905464911818390882192901883104039350105285757995782376058970382205463192526628231366854662473466838863987148898819243940809068605863725041711337107340279029811816555169181781669826715177100102639379572663639848699896757952171115689208069972249342540932428107175784150214806633479073061672324629925288020557720111253896992657435200329511186117042808357973613389

请帮忙。谢谢！

标签： pythonpython-3.xprime-factoring

解决方案

我对 github 实现进行了一些更改，以获得正确的输出，如下所示。

1.在python 3中，range()不会自动返回一个列表，所以我做到了list(range(n+1))

2.我做到了int(n/i-i)

import math

# return a dict or a list of primes up to N
# create full prime sieve for N=10^6 in 1 sec
def prime_sieve(n, output={}):
    nroot = int(math.sqrt(n))
    sieve = list(range(n+1))
    sieve[1] = 0

    for i in range(2, nroot+1):
        if sieve[i] != 0:
            m = int(n/i - i)
            sieve[i*i: n+1:i] = [0] * (m+1)

    if type(output) == dict:
        pmap = {}
        for x in sieve:
            if x != 0:
                pmap[x] = True
        return pmap
    elif type(output) == list:
        return [x for x in sieve if x != 0]
    else:
        return None

然后，在下面的函数中，我将默认值设为primelist=None

def get_prime_factors(n, primelist=None):
    if primelist is None:
        primelist = prime_sieve(n,output=[])

    fs = []
    for p in primelist:
        count = 0
        while n % p == 0:
            n /= p
            count += 1
        if count > 0:
            fs.append((p, count))

    return fs

现在，如果您尝试：

print(get_prime_factors(140))

你得到正确的输出：

[(2, 2), (5, 1), (7, 1)]

推荐阅读