使用Python2.7.x打印给定数字的所有因素和素数

Question

好的，这是我第一次尝试使用Python2.7编程。我需要对此代码的帮助或反馈：

1. 我如何知道这个程序所消耗的处理周期？
2. 如何使用递归实现这个想法？
3. 从列表中删除重复项目的最佳方法是什么？我不满意这个#删除列表set_of_factors = set( list_of_all_quotients ) list_of_all_quotients = list(set_of_factors)返回list_of_all_quotients中的重复元素

设计方面的制约因素如下：

1. 质数将在运行时生成。
2. 所有复合(非素数)因子只能从素数中导出。

下面是代码：

#-------------------This Function would find all the prime factors of a given number-------------

def find_prime_factors(number):
    list_of_prime_factors = []
    quotient = number
    while (quotient > 1):
        if(quotient % 2 == 0):
        #check whether the quotient is even?
            list_of_prime_factors.append(2)
            quotient = quotient / 2

        else:
        #if the quotient is odd
            for index in xrange (3, 1 + (number/2),2):
            #start the for loop at 3 and end at a number around one-half of the quotient, and test with odd numbers only
                if (quotient % index == 0 ):
                    list_of_prime_factors.append(index)
                    quotient = quotient / index

            else:
            #The number isn't even and there are no odd numbered factors for it, that is it's a prime.
                break
        #-------------------------------------

    return list_of_prime_factors


#-------------------This Function would find quotients that would result by dividing the number by it's prime factors------------------                     

def find_all_quotients(number, list_of_prime_factors = []):
    list_of_all_quotients = []

    dividend = number
    for index in list_of_prime_factors:
        dividend = dividend / index
        list_of_all_quotients.append(index)
        list_of_all_quotients.append(dividend)

    if (len(list_of_all_quotients) == 0):
        return list_of_all_quotients
    else:
        #if the last item in the list is 1, then remove it:
        if(list_of_all_quotients[-1] == 1 ):list_of_all_quotients.pop()       
        #remove the duplicate elements in the list
        set_of_factors = set(list_of_all_quotients)
        list_of_all_quotients = list(set_of_factors)    
        return list_of_all_quotients    


#This Function would find all the factors of a number 
#--by using it's prime factors and quotients (derived by dividing it by it's prime factors)                     

def find_all_factors(number, list_of_prime_factors = [] ,list_of_all_quotients = []):
    list_of_all_factors = list_of_all_quotients

    for otr_index in range(0, len(list_of_prime_factors) ):
        for inr_index in range(0, len(list_of_all_factors)):
            product = list_of_prime_factors[otr_index] * list_of_all_factors[inr_index]
            if (number % product == 0 and number != product): list_of_all_factors.append(product)

    if (len(list_of_all_factors) == 0):
        return list_of_all_factors
    else:
        #if the last item in the list is 1, then remove it:
        if(list_of_all_factors[-1]==1): list_of_all_factors.pop()
        #remove the duplicate elements in the list
        set_of_factors = set(list_of_all_factors)
        list_of_all_factors = list(set_of_factors)        
        return list_of_all_factors


#-------------------This Function would print all the prime factors of a given number------------

def print_factors(number, list_to_be_printed=[], separator=''):


        if (len(list_to_be_printed) == 0) :
        #No roots - means a prime number:
            if (separator == ''):
                print"\n\nTry again",
            else:
                print"\n\nOops {} is a prime number! So, it doesn't have any prime factors except for 1 and iself. ".format(number)
        #Composite Number:
        else:    
            factors = list_to_be_printed
            factors.sort()
            if separator == '':
            #The separator isn't specified or empty, means print all factors separated by space:
                print "\n\nAll the Factors for {} would be = ".format(number),
                for index in xrange (0, len(factors)):
                    print "{}".format(factors[index]), 
                    if (index + 1 == len(factors)):
                        pass
                    else:
                        print separator,
            else:
            #Some separator is specified, use that, and print prime numbers:
                print "\n\nThe Prime Factorization for {} would be = ".format(number),
                for index in xrange (0, len(factors)):
                    print "{}".format(factors[index]), 
                    if (index + 1 == len(factors)):
                        pass
                    else:
                        print separator,

#-------------------The Main Function Block-------------------------------------------------------        

def main():
    str_product = raw_input("Please enter a number to get its factors ")
    int_product = int(str_product)

    #------------------------------------------------------------------

    prime_factors = find_prime_factors(int_product)
    print_factors(int_product, prime_factors,'X')
    quotients = find_all_quotients(int_product, prime_factors)
    all_factors = find_all_factors(int_product, prime_factors,quotients)
    print_factors(int_product, all_factors,'')

    #-----------------------------------------------------------------   

if __name__ == "__main__":
    main()

Answer 1

下面是一些文体评论和python的观点：

如果您刚开始使用Python，我会考虑使用Py3，如果您不能使用Py3，可以使用一些__future__导入来确保您正在编写兼容的代码，并具有相同的行为，例如：

from __future__ import print_function   # print(...)
from __future__ import division         # a / b - float division, a // b - integer division

这将使向Py3的转换变得更容易。

当您将if语句折叠到一行上时，我发现很难读懂，特别是如果之后没有空行，例如：

    if(list_of_all_quotients[-1] == 1 ):list_of_all_quotients.pop()       
    #remove the duplicate elements in the list
    set_of_factors = set(list_of_all_quotients)

此外，您不需要在()表达式周围使用if，例如：

    if list_of_all_quotients[-1] == 1:
       list_of_all_quotients.pop()

    #remove the duplicate elements in the list
    set_of_factors = set(list_of_all_quotients)

在if条件中有一个pass块可以通过检查条件的负值来删除，例如：

     if (index + 1 == len(factors)):
         pass
     else:
         print separator,

可替换为：

     if index+1 != len(factors):
         print separator,

您必须非常小心地处理可变的默认参数(请参阅：“最少的惊讶”和可变的默认参数)。在许多情况下，您不需要代码中的默认参数，因为调用成功是必需的。

例如，一般情况下，您只能在不传入list_to_printed的情况下调用该函数一次，或者下一次调用会给您带来意外的结果，但是您的使用没有这个问题，因为您总是在列表中传递(建议删除默认参数)：

def print_factors(number, list_to_be_printed=[], separator=''):

为什么要递归地这样做呢？递归算法往往能够很好地将问题划分为较小的子问题--因式分解并不是这样的。python的默认递归深度相对较低，python不执行其他为递归设计的语言所执行的递归优化，因此您通常会为递归(调用堆栈)付出代价。

总的来说，算法的复杂度比需要的高得多。找到素数的一个更容易的方法是有一个生成素数的好的、可靠的算法：

下面是一个相对简单的素数生成器：

import itertools as it

def primes():
    yield 2
    sieve = {}
    for n in it.count(3, 2):
        if n not in sieve:
            sieve[n*n] = 2*n
            yield n
            continue
        a = sieve.pop(n)
        x = n + a
        while x in sieve:
            x += a
        sieve[x] = a

然后得到一个数字的主要因素：

def prime_factors(n):
    for p in primes():
        while n % p == 0:
            n //= p
            yield p
        if p*p > n:
            break
    if n > 1:
        yield n

In []:
list(prime_factors(120))

Out[]:
[2, 2, 2, 3, 5]

您可以使用collections.Counter同时保存因子和指数。

In []:
from collections import Counter
pfactors = Counter(prime_factors(120))
pfactors

Out[]:
Counter({2: 3, 3: 1, 5: 1})

所以现在唯一的素数是pfactors.keys()，它们的指数是pfactors.values()：

然后，您可以从素数及其指数生成所有的factors，方法是将所有素数与指数的每个组合一起，直到pfactor.values()。

In []:
factors = []
for exponents in it.product(*[range(e+1) for e in pfactors.values()]):
    factor = 1
    for prime, exponent in zip(pfactors.keys(), exponents):
        factor *= prime**exponent
    factors.append(factor)

factors

Out[]:
[1, 5, 3, 15, 2, 10, 6, 30, 4, 20, 12, 60, 8, 40, 24, 120]

您显然可以使用sorted()对其进行排序，例如：

In []:
sorted(factors)

Out[]:
[1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120]