Python 寻找素因数 [英] Python Finding Prime Factors

问题描述

两部分问题:

1) 试图确定 600851475143 的最大质因数，我在网上发现这个程序似乎有效.问题是，尽管我了解程序正在做什么的基础知识，但我很难弄清楚它是如何工作的.另外，我想请您解释一下您可能知道的寻找质因数的任何方法，也许无需测试每个数字，以及您的方法是如何工作的.

1) Trying to determine the largest prime factor of 600851475143, I found this program online that seems to work. The problem is, I'm having a hard time figuring out how it works exactly, though I understand the basics of what the program is doing. Also, I'd like if you could shed some light on any method you may know of finding prime factors, perhaps without testing every number, and how your method works.

这是我在网上找到的用于素数分解的代码[注意:此代码不正确.请参阅下面 Stefan 的回答以获得更好的代码.]:

Here's the code that I found online for prime factorization [NOTE: This code is incorrect. See Stefan's answer below for better code.]:

n = 600851475143
i = 2
while i * i < n:
     while n % i == 0:
         n = n / i
     i = i + 1

print (n)

#takes about ~0.01secs

2)为什么那个代码比这个代码快这么多，只是为了测试速度，除此之外没有任何实际用途?

2) Why is that code so much faster than this code, which is just to test the speed and has no real purpose other than that?

i = 1
while i < 100:
    i += 1
#takes about ~3secs

推荐答案

这个问题是我在 google 上搜索 "python prime factorization" 时出现的第一个链接.正如@quangpn88 所指出的，对于诸如 n = 4, 9, 16, ... 之类的完美平方，这个算法是错误的 (!) 但是，@quangpn88 的修复确实也不起作用，因为如果最大的质因数出现 3 次或更多次，它会产生不正确的结果，例如，n = 2*2*2 = 8 或 n = 2*3*3*3 = 54.

This question was the first link that popped up when I googled "python prime factorization". As pointed out by @quangpn88, this algorithm is wrong (!) for perfect squares such as n = 4, 9, 16, ... However, @quangpn88's fix does not work either, since it will yield incorrect results if the largest prime factor occurs 3 or more times, e.g., n = 2*2*2 = 8 or n = 2*3*3*3 = 54.

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

I believe a correct, brute-force algorithm in Python is:

def largest_prime_factor(n):
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
    return n

不要在性能代码中使用它，但它可以用于中等数量的快速测试:

Don't use this in performance code, but it's OK for quick tests with moderately large numbers:

In [1]: %timeit largest_prime_factor(600851475143)
1000 loops, best of 3: 388 µs per loop

如果要寻找完整的质因数分解，这就是蛮力算法:

If the complete prime factorization is sought, this is the brute-force algorithm:

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

这篇关于Python 寻找素因数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！