Python寻找主要因素

Question

两部分问题......

1)试图确定600851475143的最大素数因子,发现这个程序似乎在线工作,问题是我很难弄清楚它是如何工作的(我理解程序正在做什么的基础)...另外,如果您能够了解一些您可能知道找到素数的方法(可能没有测试每个数字)以及您的方法是如何工作的.

我在网上找到的主要因素代码

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)为什么代码比这段代码快得多(代码只是测试速度而没有其他真正的用途)

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

Answer 1

这个问题是我用Google搜索时弹出的第一个链接"python prime factorization".正如@ quangpn88指出的那样,这个算法对于完美的正方形是错误的(!)n = 4, 9, 16, ...但是,@ quangpn88的修正也不起作用,因为如果最大的素数因子出现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

好.所以你说你了解基础知识,但你不确定它是如何工作的.首先,这是对其源于的项目欧拉问题的一个很好的答案.我已经对这个问题做了很多研究,这是迄今为止最简单的回答.

为了解释,我会让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)

此解释使用两个while循环.关于while循环最重要的事情是它们一直运行直到它们不再存在true.

外环指出,虽然i * i不大于n(因为最大的主要因素决不会比的平方根较大n),添加1到i内循环运行后.

内循环表示虽然i均匀分为n,但n用n除以代替i.此循环持续运行,直到它不再成立.对于n=20和i=2,n被替换为10,然后再被替换5.因为2不均匀分成5,循环停止n=5和外循环结束,产生i+1=3.

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

感谢发布此内容.在了解代码的确切工作原理之前,我永远查看了代码.希望这是您在回复中寻找的内容.如果没有,请告诉我,我可以进一步解释.

Answer 3

看起来人们正在做项目欧拉的事情,你自己编写解决方案.对于其他想要完成工作的人来说,有一个primefac模块非常快速地执行非常大的数字:

#!python

import primefac
import sys

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

Answer 4

对于素数代,我总是使用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

您可以使用Miller-Rabin素性测试来检查数字是否为素数.你可以在这里找到它的Python实现.

总是使用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

Answer 5

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

我想,这是更好的代码

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]

Answer 6

"""
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]

Answer 7

def find_prime_facs(n):
  list_of_factors=[]
  i=2
  while n>1:
    if n%i==0:
      list_of_factors.append(i)
      n=n/i
      i=i-1
    i+=1  
  return list_of_factors

Answer 8

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

我认为应该是：

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

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

print (n)

Answer 9

这样做的另一种方法：

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

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

Answer 10

我的代码：

# METHOD: PRIME FACTORS
def prime_factors(n):
    '''PRIME FACTORS: generates a list of prime factors for the number given
    RETURNS: number(being factored), list(prime factors), count(how many loops to find factors, for optimization)
    '''
    num = n                         #number at the end
    count = 0                       #optimization (to count iterations)
    index = 0                       #index (to test)
    t = [2, 3, 5, 7]                #list (to test)
    f = []                          #prime factors list
    while t[index] ** 2 <= n:
        count += 1                  #increment (how many loops to find factors)
        if len(t) == (index + 1):
            t.append(t[-2] + 6)     #extend test list (as much as needed) [2, 3, 5, 7, 11, 13...]
        if n % t[index]:            #if 0 does else (otherwise increments, or try next t[index])
            index += 1              #increment index
        else:
            n = n // t[index]       #drop max number we are testing... (this should drastically shorten the loops)
            f.append(t[index])      #append factor to list
    if n > 1:
        f.append(n)                 #add last factor...
    return num, f, f'count optimization: {count}'

我将其与得票最多的代码进行了比较，速度非常快

    def prime_factors2(n):
        i = 2
        factors = []
        count = 0                           #added to test optimization
        while i * i <= n:
            count += 1                      #added to test optimization
            if n % i:
                i += 1
            else:
                n //= i
                factors.append(i)
        if n > 1:
            factors.append(n)
        return factors, f'count: {count}'   #print with (count added)

测试，（注意，我在每个循环中添加了一个 COUNT 来测试优化）

# >>> prime_factors2(600851475143)
# ([71, 839, 1471, 6857], 'count: 1472')
# >>> prime_factors(600851475143)
# (600851475143, [71, 839, 1471, 6857], 'count optimization: 494')

我认为可以轻松修改此代码以获得（最大因子）或任何其他需要的东西。我对任何问题持开放态度，我的目标是针对更大的素数和因子进一步改进这一点。

Answer 11

如果您正在寻找维护良好的预先编写的代码，请使用来自SymPy的函数sympy.ntheory.primefactors。

它返回 的素因数的排序列表n。

>>> from sympy.ntheory import primefactors
>>> primefactors(6008)
[2, 751]

将列表传递给以max()获得最大的素数：max(primefactors(6008))

如果您想要质因数n以及它们中的每一个的多重性，请使用sympy.ntheory.factorint。

给定一个正整数n，factorint(n)返回一个字典，其中包含n作为键的质因数和作为值的它们各自的重数。

>>> from sympy.ntheory import factorint
>>> factorint(6008)   # 6008 = (2**3) * (751**1)
{2: 3, 751: 1}

该代码针对 Python 3.6.9 和 SymPy 1.1.1 进行了测试。