质因数分解python模板
作者:
endinggy
,
2021-06-11 03:25:25
,
所有人可见
,
阅读 339
prime = []
import math
def isprime(num):#判断一个数是否为素数
for p in prime:
if p > math.sqrt(num):
break
if num % p == 0:
return False
return True
MAX = 10 ** 3 + 1
def init_prime():#初始化素数集合
for i in range(2, MAX):
if isprime(i):
prime.append(i)
init_prime()
dic = {p: 0 for p in prime}
def solve(num):
for p in prime:
if p > math.sqrt(num):
break
if num == 1:
break
while num % p == 0:
dic[p] += 1
num //= p
if num > 1:
if num not in dic:
dic[num] = 0
dic[num] += 1