大数的质因数分解

Question

大数的质因数分解

3

我编写了以下代码用于求任意给定数字的最大质因数。对于小于9位数的数字，它能正常工作，但是当数字超过九位数时，它表现得不确定。如何进行优化？

此函数用于判断一个数字是否为质数。

def is_prime(x):
    u = 1
    i = 2
    while i < x:
        if x%i == 0:
            u = 0
            break
        else:
            i = i+1
    return u

该函数确定一个数字是否是另一个数字的质因数

def detprime(x,y):
    if x%y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

这个部分检查给定数字的所有质因子，将它们存储在一个列表中，并返回最大值

def functionFinal(x):
    import math
    factors = []
    y = x//2
    for i in range(1,y):
        if detprime(x,i) == 1:
            factors.append(i)
    y = len(factors)
    print(factors[y-1])

import time
start_time = time.process_time()
print("Enter a number")
num = int(input())
functionFinal(num)

print(time.process_time()-start_time)

- Wybe Turing

仅检查到x的平方根。 - Klaus D.

1

你可以使用这个答案中解释的函数来加快质数检查器的速度。 - Filip Młynarski

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Deepak Saini · Accepted Answer

你可以通过使用更有效的素数检查函数来改进代码。此外，你只需要存储列表factors的最后一个元素。同时，你可以通过JIT编译函数和使用并行化来提高速度。在下面的代码中，我使用了numba。

import math
import numba as nb

@nb.njit(cache=True)
def is_prime(n):
    if n % 2 == 0 and n > 2: 
        return 0
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return 0
    return 1

@nb.njit(cache=True)
def detprime(x, y):
    if x % y == 0:
        if (is_prime(y)):
            return 1
        else:
            return 0
    else:
        return 0

@nb.njit(parallel=True)
def functionFinal(x):
    factors = [1]
    y = x // 2
    for i in nb.prange(1, y): # check in parallel
        if detprime(x, i) == 1:
            factors[-1] = i

    return factors[-1]

好的，那么

functionFinal(234675684)

这里有性能比较结果：

你的代码 : 21.490秒

Numba版本（无并行）：0.919秒

Numba版本（有并行）：0.580秒

希望对你有所帮助。