总理分解python

Question

我对python很陌生，我想我会创建一个返回给定数字的主要因子的程序。这是我的代码：

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

与您的代码的问题是，你反复地做一些昂贵的计算在呼叫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 2

您的问题绝对不是小864.而是用于数字的复杂性，当你这样做：

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

你在做什么本质上是通过所有可能的素数每次没有按时间去不会减少。这是多余的，因为无论如何你只需要通过列表。

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

如果你只是删除while声明，你将能够更快地得到结果。

（请注意，我与费迪南德拜尔的关于上述大量的评论表示赞同。我只是说，在特定的情况下，864不是一个很大的数字，并有一个在你的程序中的错误。）

Answer 3

这是最快的一个;

n = 600851475143 
i = 2 

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

您可以在here找到该方法的说明。 n是数字和i素因素。

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]