python求 质因数分解

质因数分解： 将一个正整数以质数乘积方式表示。如60=2*2*3*5

def get_prime(n):
    primes = []
    i=2
    while n!=1:
        while n%i==0:
            n=n/i
            primes.append(i)
        i = i+1
    return  primes

def fun(n):
    my_primes = get_prime(n)
    print('%s的质数为'%n + str(my_primes))

fun(60)

这是最简单的方式

如果我们需要批量去进行质因数分解，可以考虑下面的方式，批量数量比较多的情况下，下面这种方式的时间复杂度会相对较低

获取n范围内的质数
def prime_list(n):
    my_list = list(range(n+1))

    for i in my_list:
        if i <2:
            continue
        j=2
        while i*j<= n:
            my_list[i*j] = 0
            j = j+1

    new_list = []
    for i in my_list:
        if i>1:
            new_list.append(i)
    return new_list

def get_prime(n,p):
    primes = []
    i = 0
    while n!=1:
        while n%p[i]==0:
            primes.append(p[i])
            n = n/p[i]
        i = i+1
    return primes

p = prime_list(500)

def fun(n):    
    my_primes = get_prime(n,p)
    print('%s的质数为'%n + str(my_primes))

fun(500)
fun(450)
fun(386)

质因数分解