python:计算自然数的所有因素的列表

Question

我是python的新手，我正试图弄清楚如何在python中编写一个函数，该函数会给我一个计算自然数的所有因素的列表。输入的数字不应出现在结果列表中。

它应该是这样的：

realfactor(250)
[1, 2, 5, 10, 25, 50, 125]

我可能应该这样开始：

def realfactor(n):
factorlist = []

我将感谢的帮助

Answer 1

通过所有可能因素的简单迭代来构建可行因素的列表：

def realfactor(n):
    factorlist = []
    for i in range(1, n//2 + 1): # check all 1 <= i <= 1/2 of n
        if n % i == 0:           # i is a factor of n
            factorlist.append(i)
    print(factorlist)

Answer 2

def realfactor(n):
    factors = [1]
    for i in range(2, math.floor( math.sqrt(n) )+1 ):
        if n % i == 0:
            factors.append(i)
            factors.append(i/n)
    return sorted(factors)

对于非常大的n，这将比savanto的答案略快。

Answer 3

1。从这篇文章中获得的解决方案，并为python 3.x:添加了导入

from functools import reduce
def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
factors(250)
#~ {1, 2, 5, 10, 50, 25, 250, 125}

读起来很恐怖！

---

2.如果你不在乎订单，这里有一个快速订单：

def factors(n):
    return [val for sublist in [
            (i, n//i) for i in range(1, int(n**0.5) + 1) if n % i == 0
        ] for val in sublist
    ]
print(factors(250))
#~ [1, 250, 2, 125, 5, 50, 10, 25]

---

3。效率不高，但可读性和Python性更强：

def factors(n):
    fac_up = []
    fac_down = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            fac_up.append(i)
            fac_down.append(n//i)
    fac_up.extend(reversed(fac_down))
    return fac_up
print(factors(250))
#~ [1, 2, 5, 10, 25, 50, 125, 250]

---

比较

from timeit import timeit
n = 250
# sorted
def factors_a(n=n):
    factorlist = []
    for i in range(1, n//2 + 1): # check all 1 <= i <= 1/2 of n
        if n % i == 0:           # i is a factor of n
            factorlist.append(i)
    return factorlist
# partially sorted ?!
def factors_b(n=n):    
    from functools import reduce
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))
# unsorted
def factors_c(n=n):
    return [val for sublist in [
            (i, n//i) for i in range(1, int(n**0.5) + 1) if n % i == 0
        ] for val in sublist
    ]
# unsorted
def factors_d(n=n):
    factorlist = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            factorlist.extend((i, n//i))
    return factorlist
# sorted
def factors_e(n=n):
    fac_up = []
    fac_down = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            fac_up.append(i)
            fac_down.append(n//i)
    fac_up.extend(reversed(fac_down))
    return fac_up
# sorted
def factors_f(n=n):
    import math
    factors = [1]
    for i in range(2, math.floor( math.sqrt(n) )+1 ):
        if n % i == 0:
            factors.append(i)
            factors.append(i/n)
    return sorted(factors)

def test():
    global n
    for i in [12, 250, 10000, 99887766554433221100]:
        print("--- TEST RUN, n = %i ---" % i)
        n = i
        for func in (factors_a, factors_b, factors_c, factors_d, factors_e, factors_f):
            print(func.__name__, timeit(func, number=50000))
    print("--- DONE ---")
test()

定时

--- TEST RUN, n = 12 ---
factors_a 3.6315924063687817
factors_b 2.066486179519643
factors_c 1.1868003486015368
factors_d 0.9670367921808065
factors_e 1.3348606748124894
factors_f 1.7466818274729121
--- TEST RUN, n = 250 ---
factors_a 3.873070439592084
factors_b 2.060870580367009
factors_c 1.1865506143719813
factors_d 0.9752904229490014
factors_e 1.3438553833548212
factors_f 1.752019469006882
--- TEST RUN, n = 10000 ---
factors_a 3.5701808777132555
factors_b 2.0908904308173533
factors_c 1.2107483217776007
factors_d 0.9822444949425062
factors_e 1.3818273874635452
factors_f 1.75292261745426
--- TEST RUN, n = 99887766554433221100 ---
factors_a 3.4753276265071236
factors_b 2.066540915789119
factors_c 1.203012119807454
factors_d 0.9725134125242221
factors_e 1.362277986697336
factors_f 1.7789864895491974
--- DONE ---