給定一個 number n，我想生成一個所有唯一除數的排序串列n（沒有重復）。解決這個問題真的很簡單，但我感興趣的是效率。最快的方法是什么？
這是一種使用純python的方法：
def get_divisors(n):
"""
:param n: positive integer.
:return: list of all different divisors of n.
"""
if n <= 0:
return []
divisors = [1, n]
for div in range(1, int(n ** 0.5 1)):
if n % div == 0:
divisors.extend([n // div, div])
return sorted(list(set(divisors)))
關于如何優化它的任何建議？歡迎使用 Numpy 和其他優化的庫。
uj5u.com熱心網友回復：
您已經進行了平方根優化。接下來是利用 numpy 的并行性：
import numpy as np
def npDivs(N):
divs = np.arange(1,int(N**0.5) 1) # potential divisors up to √N
divs = divs[N % divs==0] # divisors
comp = N//divs[::-1] # complement quotients
return np.concatenate((divs,comp[divs[-1]==comp[0]:])) # combined
print(getDivs(1001**2))
[ 1 7 11 13 49 77 91 121 143
169 539 637 847 1001 1183 1573 1859 5929
7007 8281 11011 13013 20449 77077 91091 143143 1002001]
comp[divs[-1]==comp[0]:] 如果它是整數，則避免重復平方根。
一種更快的方法是獲取素數并將它們組合成一個結果集：
def getDivs(N):
factors = {1}
maxP = int(N**0.5)
p,inc = 2,1
while p <= maxP:
while N%p==0:
factors.update([f*p for f in factors])
N //= p
maxP = int(N**0.5)
p,inc = p inc,2
if N>1:
factors.update([f*N for f in factors])
return sorted(factors)
基準：
from timeit import timeit
N = 1010101**2
print(timeit(lambda:getDivs(N),number=100)) # 0.0015
print(timeit(lambda:npDivs(N),number=100)) # 0.9753
print(timeit(lambda:get_divisors(N),number=100)) # 8.5605
uj5u.com熱心網友回復：
由于假設輸入不大于 10 億，因此您可以使用作為基本試驗除法改進的Wheel 分解（帶有基）來計算主要因子。{2, 3}這很快，因為素數因子的數量總是很少（不超過 30 個值）。然后，您可以將主要因素轉換為除數串列（可能有數千個專案）。使用Numba 即時編譯器(JIT) 可以有效地計算分解。這是生成的代碼：
import numba as nb
@nb.njit('List(int_)(int_)')
def get_prime_divisors(n):
divisors = []
while n % 2 == 0:
divisors.append(2)
n //= 2
while n % 3 == 0:
divisors.append(3)
n //= 3
i = 5
while i*i <= n:
for k in (i, i 2):
while n % k == 0:
divisors.append(k)
n //= k
i = 6
if n > 1:
divisors.append(n)
return divisors
@nb.njit('List(int_)(int_)')
def get_divisors(n):
divisors = []
if n == 1:
divisors.append(1)
elif n > 1:
prime_factors = get_prime_divisors(n)
divisors = [1]
last_prime = 0
factor = 0
slice_len = 0
# Find all the products that are divisors of n
for prime in prime_factors:
if last_prime != prime:
slice_len = len(divisors)
factor = prime
else:
factor *= prime
for i in range(slice_len):
divisors.append(divisors[i] * factor)
last_prime = prime
divisors.sort()
return divisors
以下是我機器上 5000 個介于 1 到 100 萬之間的隨機整數的計時：
Initial get_divisors: 125 ms
Alain's getDivs: 40 ms
Tim Peters' get_divisors: 87 ms
This solution: 7 ms
以下是我機器上 2000 個介于 1 到 10 億之間的隨機整數的計時：
Initial get_divisors: 1403 ms
Alain's getDivs: 231 ms
Tim Peters' get_divisors: 178 ms
This solution: 8 ms
因此，該解決方案比最快的替代解決方案快 6~22 倍，比初始實施快 18~175 倍。
uj5u.com熱心網友回復：
我希望最快的方法是從輸入的完整素數分解中“從頭開始”構建除數。但是你不會在這里得到關于“最快的方法”的答案來開始一個素因數分解：這本身就是一個巨大的話題，對于大整數來說仍然是一個非常活躍的研究領域。
下面的方法簡單地使用試除法，向上通過剩余因子的平方根，但跳過 2 和 3 的倍數（除了 2 和 3 本身）。通過 32 位整數，這是相當快的。
給定一個素數分解
n == p0**e0 * p1**e1 * p2**e2 ...
那么 的除數n是所有且僅是指數小于或等于 的該形式的整數e0, e1, e2, ...。itertools.product()可以直接生成所有這樣的指數元組，然后只需進行冪運算并將結果相乘即可。
def get_divisors(n):
from math import isqrt, prod
from itertools import accumulate, chain, cycle, product
if n <= 1:
return [n]
ps = []
exps = []
limit = isqrt(n)
for cand in chain([2, 3], accumulate(cycle([2, 4]),
initial=5)):
if cand > limit:
break
if n % cand == 0:
count = 1
n //= cand
while n % cand == 0:
count = 1
n //= cand
ps.append(cand)
exps.append(count)
limit = isqrt(n)
if n > 1:
ps.append(n)
exps.append(1)
result = []
for pows in product(*(range(exp 1) for exp in exps)):
result.append(prod(p**e for p, e in zip(ps, pows)))
return sorted(result)
>>> for i in range(22):
... print(i, get_divisors(i))
0 [0]
1 [1]
2 [1, 2]
3 [1, 3]
4 [1, 2, 4]
5 [1, 5]
6 [1, 2, 3, 6]
7 [1, 7]
8 [1, 2, 4, 8]
9 [1, 3, 9]
10 [1, 2, 5, 10]
11 [1, 11]
12 [1, 2, 3, 4, 6, 12]
13 [1, 13]
14 [1, 2, 7, 14]
15 [1, 3, 5, 15]
16 [1, 2, 4, 8, 16]
17 [1, 17]
18 [1, 2, 3, 6, 9, 18]
19 [1, 19]
20 [1, 2, 4, 5, 10, 20]
21 [1, 3, 7, 21]
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/410076.html
標籤：