Python 寻找素因数

Python Finding Prime Factors

提问by francium

Two part question:

两部分问题：

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.

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

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

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

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) 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?

2）为什么那个代码比这个代码快这么多，这只是测试速度，除此之外没有真正的目的？

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

回答by Ashwini Chaudhary

For prime number generation I always use Sieve of Eratosthenes:

对于素数生成，我总是使用Sieve of Eratosthenes：

def primes(n):
    if n<=2:
        return []
    sieve=[True]*(n+1)
    for x in range(3,int(n**0.5)+1,2):
        for y in range(3,(n//x)+1,2):
            sieve[(x*y)]=False

    return [2]+[i for i in range(3,n,2) if sieve[i]]

In [42]: %timeit primes(10**5)
10 loops, best of 3: 60.4 ms per loop

In [43]: %timeit primes(10**6)
1 loops, best of 3: 1.01 s per loop

You can use Miller-Rabin primality testto check whether a number is prime or not. You can find its Python implementations here.

您可以使用Miller-Rabin 素数检验来检查数字是否为素数。您可以在此处找到它的 Python 实现。

Always use timeitmodule to time your code, the 2nd one takes just 15us:

始终使用timeit模块来为您的代码计时，第二个只需15us：

def func():
    n = 600851475143
    i = 2
    while i * i < n:
         while n % i == 0:
            n = n / i
         i = i + 1

In [19]: %timeit func()
1000 loops, best of 3: 1.35 ms per loop

def func():
    i=1
    while i<100:i+=1
   ....:     

In [21]: %timeit func()
10000 loops, best of 3: 15.3 us per loop

回答by Will Luce

Ok. So you said you understand the basics, but you're not sure EXACTLY how it works. First of all, this is a great answer to the Project Euler question it stems from. I've done a lot of research into this problem and this is by far the simplest response.

好的。所以你说你了解基础知识，但你不确定它是如何工作的。首先，这是对它源自的 Project Euler 问题的一个很好的回答。我对这个问题做了很多研究，这是迄今为止最简单的回应。

For the purpose of explanation, I'll let n = 20. To run the real Project Euler problem, let n = 600851475143.

出于解释的目的，我会让n = 20. 要运行真正的 Project Euler 问题，让n = 600851475143.

n = 20 
i = 2

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

print (n)

This explanation uses two whileloops. The biggest thing to remember about whileloops is that they run until they are no longer true.

这个解释使用了两个while循环。关于while循环需要记住的最重要的事情是它们会一直运行，直到它们不再是true。

The outer loop states that while i * iisn't greater than n(because the largest prime factor will never be larger than the square root of n), add 1to iafter the inner loop runs.

外循环声明 whilei * i不大于n（因为最大的质因数永远不会大于 的平方根n），在内循环运行后1加到i。

The inner loop states that while idivides evenly into n, replace nwith ndivided by i. This loop runs continuously until it is no longer true. For n=20and i=2, nis replaced by 10, then again by 5. Because 2doesn't evenly divide into 5, the loop stops with n=5and the outer loop finishes, producing i+1=3.

内回路指出，虽然i平均划分n，取代n与n由分割i。这个循环持续运行，直到它不再为真。对于n=20和i=2，n被替换为10，然后又被替换为5。因为2不均匀分成5，循环停止，n=5外循环结束，产生i+1=3。

Finally, because 3squared is greater than 5, the outer loop is no longer trueand prints the result of n.

最后，因为3平方大于5，外循环不再true打印 的结果n。

Thanks for posting this. I looked at the code forever before realizing how exactly it worked. Hopefully, this is what you're looking for in a response. If not, let me know and I can explain further.

感谢您发布此信息。在意识到它究竟是如何工作之前，我一直看着代码。希望这是您在回复中寻找的内容。如果没有，请告诉我，我可以进一步解释。

回答by quangpn88

The code is wrong with 100. It should check case i * i = n:

代码错误为 100。它应该检查 case i * i = n：

I think it should be:

我觉得应该是：

while i * i <= n:
    if i * i = n:
        n = i
        break

    while n%i == 0:
        n = n / i
    i = i + 1

print (n)

回答by rubslopes

You shouldn't loop till the square root of the number! It may be right some times, but not always!

你不应该循环到数字的平方根！有时可能是对的，但并非总是如此！

Largest prime factor of 10 is 5, which is bigger than the sqrt(10) (3.16, aprox).

10 的最大质因数是 5，比 sqrt(10) (3.16, aprox) 大。

Largest prime factor of 33 is 11, which is bigger than the sqrt(33) (5.5,74, aprox).

33 的最大质因数是 11，比 sqrt(33) (5.5,74, aprox) 大。

You're confusing this with the propriety which states that, if a number has a prime factor bigger than its sqrt, it has to have at least another one other prime factor smaller than its sqrt. So, with you want to test if a number is prime, you only need to test till its sqrt.

您将此与适当性混淆了，即如果一个数字的质因数大于其 sqrt，则它必须至少有另一个小于其 sqrt 的质因数。所以，如果你想测试一个数字是否是素数，你只需要测试直到它的 sqrt。

回答by m0rpheu5

Isn't largest prime factor of 27 is 3 ?? The above code might be fastest,but it fails on 27 right ? 27 = 3*3*3 The above code returns 1 As far as I know.....1 is neither prime nor composite

27 的最大质因数不是 3 吗？？上面的代码可能是最快的，但它在 27 上失败了，对吗？27 = 3*3*3 上面的代码返回 1 据我所知.....1 既不是质数也不是合数

I think, this is the better code

我认为，这是更好的代码

def prime_factors(n):
    factors=[]
    d=2
    while(d*d<=n):
        while(n>1):            
            while n%d==0:
                factors.append(d)
                n=n/d
            d+=1
    return factors[-1]

回答by Stefan

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 = 8or n = 2*3*3*3 = 54.

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

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

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

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

回答by Rajesh

Another way of doing this:

这样做的另一种方法：

import sys
n = int(sys.argv[1])
result = []
for i in xrange(2,n):
    while n % i == 0:
        #print i,"|",n
        n = n/i
        result.append(i)

    if n == 1: 
        break

if n > 1: result.append(n)
print result

sample output :
python test.py 68
[2, 2, 17]

示例输出：
python test.py 68
[2, 2, 17]

回答by madGambol

Another way that skips even numbers after 2 is handled:

处理 2 后跳过偶数的另一种方法：

def prime_factors(n):
   factors = []
   d    = 2
   step = 1
   while d*d <= n:
      while n>1:
         while n%d == 0:
            factors.append(d)
            n = n/d
        d += step
        step = 2

  return factors

回答by brian d foy

It looks like people are doing the Project Euler thing where you code the solution yourself. For everyone else who wants to get work done, there's the primefac modulewhich does very large numbers very quickly:

看起来人们正在做 Project Euler 的事情，你自己编写解决方案。对于其他想要完成工作的人，有一个primefac 模块可以非常快速地处理非常大的数字：

#!python

import primefac
import sys

n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

回答by renormalizedQuanta

"""
The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

"""

from sympy import primefactors
print primefactors(600851475143)[-1]