加速素因式分解

Question

我编写了以下代码，用于返回主要因素列表。有提高速度的建议吗？

import math
def is_prime(num):
    for n in range(2,math.floor(math.sqrt(num)+1)):
        if num%n==0:
            return False
    return True         

def find_prime_factors(num):
    primes=[]
    for n in range(2,math.floor(num/2)+2):#The maximum value of the factor could only be half of the number
        if is_prime(num):
            primes.append(math.floor(num))
            break
        if is_prime(n) and num %n==0:
            num=num/n
            primes.append(n)
            while num%n ==0:
                num=num/n
                primes.append(n)

    return(primes)      

Answer 1

正确性

1不是主要因素：

>>> find_prime_factors(25)
[5, 5, 1]

性能

原始性测试是昂贵的。在is_prime()主循环的每次迭代中调用find_prime_factors()两次。此外，is_prime()以与find_prime_factors()一样的方式执行试用部门，从而导致了冗余工作。

Answer 2

考虑一个数num，它是两个大素数的乘积。假设num =127x127。你有一个n= 2，3，4，5，6的循环.每一次循环，你都会检查127 x 127是否是素数。每次你发现它不是。这是非常，非常低效的。

接下来，检查每个数字n= 2，3，4，5，6，.看看它是否是素数。这里有一个技巧:一个数的最小因子n，≥，2必须是素数。因为如果它不是素数，假设n = p*q，那么p和q是n的小因子，因此n不是最小因子。这是个矛盾，所以假设n可能不是素数，一定是假的。所以你根本不需要测试n是素数。

就像其他人说的那样，你需要注意的情况是，最高的素数因子是正方形或立方体等，例如25，这里的因数是1，这不是素因子，但必须完全忽略。

还有一个技巧，就是快速检查潜在除数:唯一的偶数素数是n= 2。所以首先检查num是否可以被2整除，然后检查n= 3、5、7、9、11等数字。

另一个诀窍是: 3是唯一的素数，它是3的倍数，所以先除以2和3，然后检查数字n= 5，7，11，13，17，19，23，25。如何创建这个序列？从n= 5开始，然后添加2和4，跳过数字9、15、21，它们都是3的倍数。为此，从n=5开始，添加=2。然后设置n=n+ add和add =6- add。此选项根据需要添加= 2、4、2、4、2、4等。