Python寻找主要因素

Question

两部分问题：1）试图确定600851475143的最大素数，我在网上找到了该程序，该程序似乎有效。问题是，尽管我了解程序的基本功能，但我很难弄清楚它的工作原理。另外，我想请您介绍一下可能知道的寻找主要因素的任何方法（也许无需测试每个数字）以及您的方法如何工作。这是我在网上找到的用于质因子分解的代码：n = 600851475143i = 2while i * i < n:     while n % i == 0:         n = n / i     i = i + 1print (n)#takes about ~0.01secs2）为什么该代码比仅用于测试速度并且没有其他实际目的的代码要快得多？i = 1while i < 100:    i += 1#takes about ~3secs

Answer 1

这个问题是我在Google搜寻时弹出的第一个链接"python prime factorization"。如@ quangpn88所指出的，该算法对于诸如的完美平方是错误的（！）。n = 4, 9, 16, ...但是，@ quangpn88的修复也不起作用，因为如果最大素数出现3次或3次以上（例如n = 2*2*2 = 8或），它将产生错误的结果n = 2*3*3*3 = 54。

我相信Python中正确的蛮力算法是：

def largest_prime_factor(n):

    i = 2

    while i * i <= n:

        if n % i:

            i += 1

        else:

            n //= i

    return n

不要在性能代码中使用此方法，但是对于数量较大的快速测试也可以：

In [1]: %timeit largest_prime_factor(600851475143)

1000 loops, best of 3: 388 µs per loop

如果寻求完整的素数分解，则为蛮力算法：

def prime_factors(n):

    i = 2

    factors = []

    while i * i <= n:

        if n % i:

            i += 1

        else:

            n //= i

            factors.append(i)

    if n > 1:

        factors.append(n)

    return factors

Answer 2

好像人们在做Euler项目一样，您自己编写解决方案。对于想要完成工作的其他所有人，有primefac模块可以非常快速地完成大量工作：

#!python

import primefac

import sys

n = int( sys.argv[1] )

factors = list( primefac.primefac(n) )

print '\n'.join(map(str, factors))