在將其標(biāo)記為重復(fù)之前...我需要找到 n 的所有因數(shù)（有很多解決方案）。我能夠?qū)崿F(xiàn)的最快的一個(gè)是循環(huán)遍歷 2 到 sqrt of 的范圍n。這是我到目前為止...def get_factors(n): factors = set() for i in range(2, int(math.sqrt(n) + 1)): if n % i == 0: factors.update([i, n // i]) return factors這是找到 的因數(shù)的一種非?？焖俚姆椒╪，但我想知道是否有更快的方法來(lái)找到 的因數(shù)n。唯一的限制是我只能在 Python 3.7 中使用數(shù)學(xué)庫(kù)。關(guān)于如何更快地完成此操作的任何想法？我找不到只使用數(shù)學(xué)庫(kù)的答案。我可以做些什么來(lái)提高我當(dāng)前算法的效率嗎？
2 回答
RISEBY
TA貢獻(xiàn)1856條經(jīng)驗(yàn) 獲得超5個(gè)贊
最好在計(jì)算素?cái)?shù)時(shí)獲取因數(shù)，這樣您就可以避免額外的工作，以防萬(wàn)一您在篩子完成之前完成因數(shù)分解。更新后的代碼將是：
def factors(number):
n=int(number**.5)+1
x=number
divisors=[]
era =[1] * n
primes=[]
for p in range(2, n):
if era[p]:
primes.append(p)
while x%p==0:
x//=p
divisors.append(p)
for i in range(p*p, n, p):
era[i] = False
if x!=1:
divisors.append(x)
return divisors
解決方案：
使用Erathostenes Sieve得到 2 和 sqrt(n) 之間的質(zhì)因數(shù)，然后檢查哪些是 n 的約數(shù)。這將大大減少代碼的運(yùn)行時(shí)間。
Erathostenes 篩法只使用列表、操作%,>=,<=和布爾值。
這是一個(gè)比我分享給您的鏈接中的實(shí)現(xiàn)更短的實(shí)現(xiàn)：
def factors(number):
n=int(number**.5)+1
era =[1] * n
primes=[]
for p in range(2, n):
if era[p]:
primes.append(p)
for i in range(p*p, n, p):
era[i] = False
divisors=[]
x=number
for i in primes:
while x%i==0:
x//=i
divisors.append(i)
if x!=1:
divisors.append(x)
return divisors
MM們
TA貢獻(xiàn)1886條經(jīng)驗(yàn) 獲得超2個(gè)贊
找到數(shù)字所有因素的最快方法
約束——不要使用除數(shù)學(xué)之外的任何外部庫(kù)
測(cè)試了4種方法
審判部門(mén)（提問(wèn)者@HasnainAli 發(fā)布的代碼）又名審判
Eratosthenes Sieve（來(lái)自@MonsieurGalois 帖子）又名 Sieve
素因數(shù)分解的靈感來(lái)自aka Factorize
Primes based on Wheel Factorization 靈感來(lái)自Wheel Factorization aka Wheel
結(jié)果
結(jié)果是相對(duì)于試分的，即（試分時(shí)間）÷（其他方法時(shí)間）
使用 timeit 的 @Davakar使用Benchit 的基準(zhǔn)測(cè)試
N trial sieve prime_fac wheel_fac
1 1.0 1.070048 1.129752 1.104619
2 1.0 1.438679 3.201589 1.119284
4 1.0 1.492564 2.749838 1.176149
8 1.0 1.595604 3.164555 1.290554
16 1.0 1.707575 2.917286 1.172851
32 1.0 2.051244 3.070331 1.262998
64 1.0 1.982820 2.701439 1.073524
128 1.0 2.188541 2.776955 1.098292
256 1.0 2.086762 2.442863 0.945812
512 1.0 2.365761 2.446502 0.914936
1024 1.0 2.516539 2.076006 0.777048
2048 1.0 2.518634 1.878156 0.690900
4096 1.0 2.546800 1.585665 0.573352
8192 1.0 2.623528 1.351017 0.484521
16384 1.0 2.642640 1.117743 0.395437
32768 1.0 2.796339 0.920231 0.327264
65536 1.0 2.757787 0.725866 0.258145
131072 1.0 2.790135 0.529174 0.189576
262144 1.0 2.676348 0.374986 0.148726
524288 1.0 2.877928 0.269510 0.107237
1048576 1.0 2.522501 0.189929 0.080233
2097152 1.0 3.142147 0.125797 0.053157
4194304 1.0 2.673095 0.105293 0.045798
8388608 1.0 2.675686 0.075033 0.030105
16777216 1.0 2.508037 0.057209 0.022760
33554432 1.0 2.491193 0.038634 0.015440
67108864 1.0 2.485025 0.029142 0.011826
134217728 1.0 2.493403 0.021297 0.008597
268435456 1.0 2.492891 0.015538 0.006098
536870912 1.0 2.448088 0.011308 0.004539
1073741824 1.0 1.512157 0.005103 0.002075
結(jié)論：
篩分法總是比試分法慢（即比率列> 1）
試用師最快達(dá)到 n ~256
輪分解法整體最快（即481X試分法為n = 2**30即1/0.002075~481）
代碼
方式一：原帖
import math
def trial(n):
" Factors by trial division "
factors = set()
for i in range(2, int(math.sqrt(n) + 1)):
if n % i == 0:
factors.update([i, n // i])
return factors
方法二——篩法（@MonsieurGalois post）
def factors_sieve(number):
" Using primes in trial division "
# Find primes up to sqrt(n)
n=int(number**.5)+1
era =[1] * n
primes=[]
for p in range(2, n):
if era[p]:
primes.append(p)
for i in range(p*p, n, p):
era[i] = False
# Trial division using primes
divisors=[]
x=number
for i in primes:
while x%i==0:
x//=i
divisors.append(i)
if x!=1:
divisors.append(x)
return divisors
方法三——基于質(zhì)因數(shù)分解求除數(shù)
靈感來(lái)自
def generateDivisors(curIndex, curDivisor, arr):
" Yields the next factor based upon prime exponent "
if (curIndex == len(arr)):
yield curDivisor
return
for i in range(arr[curIndex][0] + 1):
yield from generateDivisors(curIndex + 1, curDivisor, arr)
curDivisor *= arr[curIndex][1]
def prime_factorization(n):
" Generator for factors of n "
# To store the prime factors along
# with their highest power
arr = []
# Finding prime factorization of n
i = 2
while(i * i <= n):
if (n % i == 0):
count = 0
while (n % i == 0):
n //= i
count += 1
# For every prime factor we are storing
# count of it's occurenceand itself.
arr.append([count, i])
i += 2 if i % 2 else 1
# If n is prime
if (n > 1):
arr.append([1, n])
curIndex = 0
curDivisor = 1
# Generate all the divisors
yield from generateDivisors(curIndex, curDivisor, arr)
方法四——輪式分解
def wheel_factorization(n):
" Factors of n based upon getting primes for trial division based upon wheel factorization "
# Init to 1 and number
result = {1, n}
# set up prime generator
primes = prime_generator()
# Get next prime
i = next(primes)
while(i * i <= n):
if (n % i == 0):
result.add(i)
while (n % i == 0):
n //= i
result.add(n)
i = next(primes) # use next prime
return result
def prime_generator():
" Generator for primes using trial division and wheel method "
yield 2; yield 3; yield 5; yield 7;
def next_seq(r):
" next in the equence of primes "
f = next(r)
yield f
r = (n for n in r if n % f) # Trial division
yield from next_seq(r)
def wheel():
" cycles through numbers in wheel whl "
whl = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6,
2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]
while whl:
for element in whl:
yield element
def wheel_accumulate(n, gen):
" accumulate wheel numbers "
yield n
total = n
for element in gen:
total += element
yield total
for p in next_seq(wheel_accumulate(11, wheel())):
yield p
測(cè)試代碼
from timeit import timeit
cnt = 100000 # base number of repeats for timeit
print('{0: >12} {1: >9} {2: >9} {3: >9} {4: >9}'.format('N', 'Trial', 'Primes', 'Division', 'Wheel'))
for k in range(1, 31):
N = 2**k
count = cnt // k # adjust repeats based upon size of k
x = timeit(lambda:trial(N), number=count)
y = timeit(lambda:sieve(N), number=count)
z = timeit(lambda:list(prime_factorization(N)), number=count)
k = timeit(lambda:list(wheel_factorization(N)), number=count)
print(f"{N:12d} {1:9d} {x/y:9.5f} {x/z:9.5f} {x/k:9.5f}")
添加回答
舉報(bào)
0/150
提交
取消