用python计算素数因子

我从头开始做的,它使用了质数筛算法的修改。

from math import sqrt
from collections import Counter
def prime_factors(lst):
    maximumnumber=max(lst)
    primesieve=[0]*(maximumnumber+1)
    primesieve[0]=1
    primesieve[1]=1
    #DOING PRIME NUMBER SIEVE
    for i in range(2,int(sqrt(maximumnumber))+1):
        if(primesieve[i]==0):
            for j in range(2*i,len(primesieve),i):
                primesieve[j]=i

    for j in range(len(lst)):
        num=lst[j]
        factors=[]
        #take each number(num) and divided it by a prime number (primesieve[num])
        #do it until you find no more prime factors for number
        while(primesieve[num]>0):

            factors.append(primesieve[num])
            num=num//primesieve[num]
        factors.append(num)
        yield Counter(factors)

for i in prime_factors([3,4,6]):
    print(i)

输出

Counter({3: 1})
Counter({2: 2})
Counter({2: 1, 3: 1})

我来解释一下我做了什么

1. 使用素数筛选算法找到列表中0和最大元素之间的素数, Link 对于算法的一部分,我只是修改了算法的一部分,而不是使用素数数组作为布尔值,整数来显示它与哪个数相除
2. 遍历这些数字,找出所有的素因子