仅使用数学库更快地查找 n 的因数

Question

在将其标记为重复之前...

我需要找到 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

这是找到 的因数的一种非常快速的方法n，但我想知道是否有更快的方法来找到 的因数n。唯一的限制是我只能在 Python 3.7 中使用数学库。关于如何更快地完成此操作的任何想法？我找不到只使用数学库的答案。我可以做些什么来提高我当前算法的效率吗？

Answer 1

最好在计算素数时获取因数，这样您就可以避免额外的工作，以防万一您在筛子完成之前完成因数分解。更新后的代码将是：def factors(number):&nbsp; &nbsp; n=int(number**.5)+1&nbsp; &nbsp; x=number&nbsp; &nbsp; divisors=[]&nbsp; &nbsp; era =[1] * n&nbsp; &nbsp; primes=[]&nbsp; &nbsp; for p in range(2, n):&nbsp; &nbsp; &nbsp; &nbsp; if era[p]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; primes.append(p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while x%p==0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x//=p&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisors.append(p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i in range(p*p, n, p):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; era[i] = False&nbsp; &nbsp; if x!=1:&nbsp; &nbsp; &nbsp; &nbsp; divisors.append(x)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return divisors解决方案：使用Erathostenes Sieve得到 2 和 sqrt(n) 之间的质因数，然后检查哪些是 n 的约数。这将大大减少代码的运行时间。Erathostenes 筛法只使用列表、操作%,>=,<=和布尔值。这是一个比我分享给您的链接中的实现更短的实现：def factors(number):&nbsp; &nbsp; n=int(number**.5)+1&nbsp; &nbsp; era =[1] * n&nbsp; &nbsp; primes=[]&nbsp; &nbsp; for p in range(2, n):&nbsp; &nbsp; &nbsp; &nbsp; if era[p]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; primes.append(p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i in range(p*p, n, p):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; era[i] = False&nbsp; &nbsp; divisors=[]&nbsp; &nbsp; x=number&nbsp; &nbsp; for i in primes:&nbsp; &nbsp; &nbsp; &nbsp; while x%i==0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x//=i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisors.append(i)&nbsp; &nbsp; if x!=1:&nbsp; &nbsp; &nbsp; &nbsp; divisors.append(x)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return divisors

Answer 2

找到数字所有因素的最快方法约束——不要使用除数学之外的任何外部库测试了4种方法审判部门（提问者@HasnainAli 发布的代码）又名审判Eratosthenes Sieve（来自@MonsieurGalois 帖子）又名 Sieve素因数分解的灵感来自aka FactorizePrimes based on Wheel Factorization 灵感来自Wheel Factorization&nbsp;aka Wheel结果结果是相对于试分的，即（试分时间）÷（其他方法时间）使用 timeit 的 @Davakar使用Benchit 的基准测试N&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; trial&nbsp; sieve&nbsp; &nbsp; &nbsp;prime_fac&nbsp; wheel_fac&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 1.070048&nbsp; &nbsp;1.129752&nbsp; &nbsp;1.1046192&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 1.438679&nbsp; &nbsp;3.201589&nbsp; &nbsp;1.1192844&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 1.492564&nbsp; &nbsp;2.749838&nbsp; &nbsp;1.1761498&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 1.595604&nbsp; &nbsp;3.164555&nbsp; &nbsp;1.29055416&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 1.707575&nbsp; &nbsp;2.917286&nbsp; &nbsp;1.17285132&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.051244&nbsp; &nbsp;3.070331&nbsp; &nbsp;1.26299864&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 1.982820&nbsp; &nbsp;2.701439&nbsp; &nbsp;1.073524128&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.188541&nbsp; &nbsp;2.776955&nbsp; &nbsp;1.098292256&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.086762&nbsp; &nbsp;2.442863&nbsp; &nbsp;0.945812512&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.365761&nbsp; &nbsp;2.446502&nbsp; &nbsp;0.9149361024&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.516539&nbsp; &nbsp;2.076006&nbsp; &nbsp;0.7770482048&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.518634&nbsp; &nbsp;1.878156&nbsp; &nbsp;0.6909004096&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.546800&nbsp; &nbsp;1.585665&nbsp; &nbsp;0.5733528192&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.623528&nbsp; &nbsp;1.351017&nbsp; &nbsp;0.48452116384&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.642640&nbsp; &nbsp;1.117743&nbsp; &nbsp;0.39543732768&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.796339&nbsp; &nbsp;0.920231&nbsp; &nbsp;0.32726465536&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.757787&nbsp; &nbsp;0.725866&nbsp; &nbsp;0.258145131072&nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.790135&nbsp; &nbsp;0.529174&nbsp; &nbsp;0.189576262144&nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.676348&nbsp; &nbsp;0.374986&nbsp; &nbsp;0.148726524288&nbsp; &nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.877928&nbsp; &nbsp;0.269510&nbsp; &nbsp;0.1072371048576&nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.522501&nbsp; &nbsp;0.189929&nbsp; &nbsp;0.0802332097152&nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 3.142147&nbsp; &nbsp;0.125797&nbsp; &nbsp;0.0531574194304&nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.673095&nbsp; &nbsp;0.105293&nbsp; &nbsp;0.0457988388608&nbsp; &nbsp; &nbsp; &nbsp;1.0&nbsp; 2.675686&nbsp; &nbsp;0.075033&nbsp; &nbsp;0.03010516777216&nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.508037&nbsp; &nbsp;0.057209&nbsp; &nbsp;0.02276033554432&nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.491193&nbsp; &nbsp;0.038634&nbsp; &nbsp;0.01544067108864&nbsp; &nbsp; &nbsp; 1.0&nbsp; 2.485025&nbsp; &nbsp;0.029142&nbsp; &nbsp;0.011826134217728&nbsp; &nbsp; &nbsp;1.0&nbsp; 2.493403&nbsp; &nbsp;0.021297&nbsp; &nbsp;0.008597268435456&nbsp; &nbsp; &nbsp;1.0&nbsp; 2.492891&nbsp; &nbsp;0.015538&nbsp; &nbsp;0.006098536870912&nbsp; &nbsp; &nbsp;1.0&nbsp; 2.448088&nbsp; &nbsp;0.011308&nbsp; &nbsp;0.0045391073741824&nbsp; &nbsp; 1.0&nbsp; 1.512157&nbsp; &nbsp;0.005103&nbsp; &nbsp;0.002075结论：筛分法总是比试分法慢（即比率列> 1）试用师最快达到 n ~256轮分解法整体最快（即481X试分法为n = 2**30即1/0.002075~481）代码方式一：原帖import mathdef trial(n):&nbsp; " Factors by trial division "&nbsp; factors = set()&nbsp; for i in range(2, int(math.sqrt(n) + 1)):&nbsp; &nbsp; &nbsp; if n % i == 0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; factors.update([i, n // i])&nbsp; return factors方法二——筛法（@MonsieurGalois post）def factors_sieve(number):&nbsp; " Using primes in trial division "&nbsp; # Find primes up to sqrt(n)&nbsp; n=int(number**.5)+1&nbsp; era =[1] * n&nbsp; primes=[]&nbsp; for p in range(2, n):&nbsp; &nbsp; &nbsp; if era[p]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; primes.append(p)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for i in range(p*p, n, p):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; era[i] = False&nbsp; # Trial division using primes&nbsp; divisors=[]&nbsp; x=number&nbsp; for i in primes:&nbsp; &nbsp; &nbsp; while x%i==0:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x//=i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; divisors.append(i)&nbsp; if x!=1:&nbsp; &nbsp; &nbsp; divisors.append(x)&nbsp; &nbsp;&nbsp;&nbsp; return divisors方法三——基于质因数分解求除数灵感来自def generateDivisors(curIndex, curDivisor, arr):&nbsp;&nbsp; " Yields the next factor based upon prime exponent "&nbsp;&nbsp; if (curIndex == len(arr)):&nbsp;&nbsp; &nbsp; yield curDivisor&nbsp; &nbsp; return&nbsp; for i in range(arr[curIndex][0] + 1):&nbsp;&nbsp; &nbsp; yield from generateDivisors(curIndex + 1, curDivisor, arr)&nbsp;&nbsp; &nbsp; curDivisor *= arr[curIndex][1]def prime_factorization(n):&nbsp; &nbsp; " Generator for factors of n "&nbsp; &nbsp; # To store the prime factors along&nbsp;&nbsp; &nbsp; # with their highest power&nbsp;&nbsp; &nbsp; arr = []&nbsp;&nbsp; &nbsp; # Finding prime factorization of n&nbsp;&nbsp; &nbsp; i = 2&nbsp; &nbsp; while(i * i <= n):&nbsp;&nbsp; &nbsp; &nbsp; if (n % i == 0):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; count = 0&nbsp; &nbsp; &nbsp; &nbsp; while (n % i == 0):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n //= i&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count += 1&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # For every prime factor we are storing&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; # count of it's occurenceand itself.&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; arr.append([count, i])&nbsp; &nbsp; &nbsp; i += 2 if i % 2 else 1&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; # If n is prime&nbsp;&nbsp; &nbsp; if (n > 1):&nbsp;&nbsp; &nbsp; &nbsp; arr.append([1, n])&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; curIndex = 0&nbsp; &nbsp; curDivisor = 1&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; # Generate all the divisors&nbsp;&nbsp; &nbsp; yield from generateDivisors(curIndex, curDivisor, arr)&nbsp;方法四——轮式分解def wheel_factorization(n):&nbsp;&nbsp; &nbsp; " Factors of n based upon getting primes for trial division based upon wheel factorization "&nbsp; &nbsp; # Init to 1 and number&nbsp; &nbsp; result = {1, n}&nbsp; &nbsp; # set up prime generator&nbsp; &nbsp; primes = prime_generator()&nbsp; &nbsp;&nbsp; &nbsp; # Get next prime&nbsp; &nbsp; i = next(primes)&nbsp; &nbsp; while(i * i <= n):&nbsp;&nbsp; &nbsp; &nbsp; if (n % i == 0):&nbsp; &nbsp; &nbsp; &nbsp; result.add(i)&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; while (n % i == 0):&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; n //= i&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.add(n)&nbsp; &nbsp; &nbsp; i = next(primes)&nbsp; # use next prime&nbsp; &nbsp; return resultdef prime_generator():&nbsp; " Generator for primes using trial division and wheel method "&nbsp; yield 2; yield 3; yield 5; yield 7;&nbsp; def next_seq(r):&nbsp; &nbsp; " next in the equence of primes "&nbsp; &nbsp; f = next(r)&nbsp; &nbsp; yield f&nbsp; &nbsp; r = (n for n in r if n % f)&nbsp; # Trial division&nbsp; &nbsp; yield from next_seq(r)&nbsp; def wheel():&nbsp; &nbsp; " cycles through numbers in wheel whl "&nbsp; &nbsp; whl = [2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6,&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10]&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; while whl:&nbsp; &nbsp; &nbsp; for element in whl:&nbsp; &nbsp; &nbsp; &nbsp; yield element&nbsp; def wheel_accumulate(n, gen):&nbsp; &nbsp; " accumulate wheel numbers "&nbsp; &nbsp; yield n&nbsp; &nbsp; total = n&nbsp; &nbsp; for element in gen:&nbsp; &nbsp; &nbsp; total += element&nbsp; &nbsp; &nbsp; yield total&nbsp; for p in next_seq(wheel_accumulate(11, wheel())):&nbsp; &nbsp; yield p测试代码from timeit import timeitcnt = 100000&nbsp; # base number of repeats for timeitprint('{0: >12} {1: >9} {2: >9} {3: >9} {4: >9}'.format('N', 'Trial', 'Primes', 'Division', 'Wheel'))for k in range(1, 31):&nbsp; N = 2**k&nbsp; count = cnt // k&nbsp; &nbsp;# adjust repeats based upon size of k&nbsp; x = timeit(lambda:trial(N), number=count)&nbsp; y = timeit(lambda:sieve(N), number=count)&nbsp; z = timeit(lambda:list(prime_factorization(N)), number=count)&nbsp; k = timeit(lambda:list(wheel_factorization(N)), number=count)&nbsp; print(f"{N:12d} {1:9d} {x/y:9.5f} {x/z:9.5f} {x/k:9.5f}")