质数分解 python

Question

我是 python 的新手，我想我会创建一个程序来 returns 给定数字的质因数。这是我的代码：

import math
import operator
import functools

def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True



def factors (a):
    factorlist = []
    if isprime(a) == True:
        print "The number is a prime."
    else:   
        while functools.reduce(operator.mul, factorlist, 1) != a:
            for x in range (1, a):
                if a % x == 0:
                    if isprime(x) == True:
                        factorlist.append(x)
        factorlist.sort()
        print factorlist

testnumber = int(input("Enter a number."))
factors(testnumber)

我的问题是，根据数量的不同，需要很长时间。瞬间可以解决100或1000，但2000或864就是不行！我将运行 864 作为我的输入保留了 45 分钟，但它没有打印任何内容。我的 CPU 质量有问题吗？我是运行笔记本电脑上的程序。

Answer 1

您的问题绝对不是像 864 这样小的数字的复杂性。相反，当您这样做时：

while functools.reduce(operator.mul, factorlist, 1) != a:
    for x in range (1, a):
        ...

你所做的基本上是在每次不减少时遍历所有可能的素数。这是多余的，因为无论如何您只需要浏览一次列表。

对于 2000 这样的输入，你进入了一个无限循环，因为它永远不会减少到 2000 - 这就是为什么它只保持运行。您可以在 while 和 for 之间添加 print factorlist 以查看到底发生了什么。

如果您只删除 while 语句，您将能够更快地获得结果。

（请注意，我同意上面 Ferdinand Beyer 关于大数的评论。我只是说在您的特定情况下，864 不是一个大数，并且您的程序中存在错误。）

Answer 2

这是最快的一个；

n = 600851475143 
i = 2

while i * i < n:
    while n%i == 0:
        n /= i
        print (i)
    i += 1

您可以在中找到该方法的说明。 n 是数字，i 是质因数。

Answer 3

您的代码的问题是您在调用 functools.reduce(operator.mul, factorlist, 1) 中反复进行一些昂贵的计算，并且您反复检查 isprime(x) 是否有相同的数字（和 isprime 由于循环而本身很昂贵）。

为了避免 functools.reduce 调用，您可以简单地通过改变您在@howaboutNO 的解决方案中因式分解的数字，或者通过进行递归调用（见下文）来划分已知因子。

为了避免使用相同的值调用 isprime(x) 的开销，您可以使用 memoization，这是您工具集中的一个方便的技巧。

应用这两个，我得出以下结论：

import math

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:
            memo[x] = f(x)
        return memo[x]
    return helper

@memoize
def isprime (n):
    if n == 1:
        return False
    elif n == 2:
        return True
    else:
        for x in range (2, int(math.sqrt(n))+1):
            if n % x == 0:
                return False
                break
        else:
            return True


def factors (a):
    if a == 1:
        return []
    elif isprime(a):
        return [a]
    else:
        for x in range (2, int(math.sqrt(a))+1):
            if a % x == 0:
                return [x] + factors(a/x)

testnumber = int(input("Enter a number."))
print factors(testnumber)

它比您的代码运行得快得多。

Answer 4

这是一个基于模块化筛的更快的因式分解：

# modular sieve based on (2,3,5):
sieve_size = 2 * 3 * 5
sieve = [1, 7, 11, 13, 17, 19, 23, 29]

# all primes < sieve_size
base = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

def factors(a):
    f = []

    # remove factors of primes < sieve_size
    for b in base:
        while not a % b:
            a //= b
            f.append(b)
        if a < b*b:
            break

    # remnant fully factored?
    if a < b*b:
        if a > 1:
            f.append(a)
        return f

    # remove factors of values generated by modular sieve
    #   (We do not need to test for actual primality;
    #   because candidate values are generated in ascending order,
    #   if the value is composite, all factors of it will have
    #   already been removed)
    n = sieve_size
    while True:
        for s in sieve:
            b = n + s      # 31, 37, 41, 43, ...
            while not a % b:
                a //= b
                f.append(b)
            if a < b*b:
                break
        if a < b*b:
            if a > 1:
                f.append(a)
            return f
        n += sieve_size

然后进行快速测试：

import random
for i in range(30):
    val = random.randint(1000, 1000000)
    print(val, factors(val))

几乎立即给出

344779 [73, 4723]
376343 [11, 34213]
830823 [3, 7, 39563]
927157 [7, 11, 12041]
852641 [852641]
802619 [47, 17077]
80214 [2, 3, 29, 461]
348030 [2, 3, 3, 3, 5, 1289]
533572 [2, 2, 13, 31, 331]
317206 [2, 199, 797]
806636 [2, 2, 421, 479]
539294 [2, 7, 7, 5503]
706820 [2, 2, 5, 59, 599]
501587 [97, 5171]
759410 [2, 5, 75941]
375319 [7, 53617]
668889 [3, 3, 13, 5717]
545731 [545731]
496852 [2, 2, 124213]
309332 [2, 2, 17, 4549]
629728 [2, 2, 2, 2, 2, 11, 1789]
835342 [2, 417671]
505591 [71, 7121]
172411 [172411]
410995 [5, 13, 6323]
645451 [31, 47, 443]
369849 [3, 113, 1091]
67237 [71, 947]
505186 [2, 11, 22963]
945547 [945547]

Answer 5

除非您将其作为编程练习，否则只需使用

primefactors(testnumber)

质数分解 python

Prime factorization python

python

primes

prime-factoring