<转>快速找到整数约数集方法

佚名 5年前 (2019-04-29) Python 1815人围观抢沙发百度已收录

【背景】

　我需要从N遍历到1，当我已经判断N不符合要求时，我知道N的所有约数也是不符合的，所以所有N的约数也不用遍历。因此，对于遍历的每个N，我需要快速找到它的所有约数，放到一个集合里面，而当我遍历到N'时，如果N'在集合里，我就不需要再进行判断了（假设每次判断所需要的时间远远大于约数的判断），这样我就节省了大量的时间。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

【解决】

　　stackoverflow里面有个高效的答案，如下：

1 1 from functools import reduce
2 2 
3 3 def factors(n):    
4 4     return set(reduce(list.__add__, 
5 5                 ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

【解析】

　　1、欲找N的约数，只需要在N^1/2（根号N）范围内找到半数的约数即可，剩下的半数（大约数）可直接通过N除以小的约数找到。

　　　　因此：　　range(1,int(n**0.5)+1) --> 半数（小约数）范围

　　　　　　　　　n %i == 0 --> 半数（小约数）数值

　　　　　　　　　n // i --> 剩余半数（大约数）数值

　　2、将找到的所有约数对列表，展开为一个大的列表。

　　　　因此：　　reduce( list.__add__, (列表对) )

　　3、对于完全平方数，i == n//i，因此展开的列表中会有两个一样的数值。

　　　　因此：　　set(列表)，去掉重复值。

【效率】

　　本机运行结果供参考。

 1 %timeit factors( 10**1 )
 2 
 3 OUT：100000 loops, best of 3: 5.53 μs per loop
 4 
 5 %timeit factors( 10**2 )
 6 
 7 OUT：100000 loops, best of 3: 8.03 μs per loop
 8 
 9 %timeit factors( 10**3 )
10 
11 OUT：100000 loops, best of 3: 11.1 μs per loop
12 
13 %timeit factors( 10**6 )
14 
15 OUT：100000 loops, best of 3: 133 μs per loop
16 
17 %timeit factors( 10**10 )
18 
19 OUT：100000 loops, best of 3: 19.8 ms per loop