把一个合数用质因数相乘的形式表示出来,叫做分解质因数. 分解质因数常见方法是短除法,也可以用Python实现.文章来源:https://www.toymoban.com/news/detail-739252.html
给出三种分解质因数的代码:文章来源地址https://www.toymoban.com/news/detail-739252.html
Z=int(input('x{x∈Z}='))
print(Z,'= ',end='')
if Z<0:
Z=abs(Z)
print('-',end='')
flag=0
if Z<=1:
print(Z)
flag=1
while True:
if flag:
break
for i in range(2, int(Z+1)):
if Z%i==0:
print("%d"%i, end='')
if Z==i:
flag=1
break
print('×', end='')
Z/=i
break
n = input("合数:")
if n.isdigit():
n = int(n)
else:
print("输入非法,请输入一个合数")
exit()
if n < 2:
print("请输入一个大于2的合数")
exit()
def isZhishu(n): # 判断是否是质数
for i in range(2, n):
if n % i == 0: # 不是质数
return False
else:
return True
l0 = []
def fenjie(n):
i = 2
while i < n + 1:
if n % i == 0:
l0.append(i)
n /= i
else:
i += 1
if not isZhishu(n):
fenjie(n)
str0 = ''
for i in l0:
str0 = str0 + str(i) + "*"
str0 = str0[:-1] # 去掉最后一个星号
print("%s=%s" % (n, str0))
else:
print("%s是一个质数,请输入一个合数" %n)
#MillerRabin素数判定,结合Pollard_rho递归分解,效率极高
import random
from collections import Counter
def gcd(a, b):
if a == 0:
return b
if a < 0:
return gcd(-a, b)
while b > 0:
c = a % b
a, b = b, c
return a
def mod_mul(a, b, n):
result = 0
while b > 0:
if (b & 1) > 0:
result = (result + a) % n
a = (a + a) % n
b = (b >> 1)
return result
def mod_exp(a, b, n):
result = 1
while b > 0:
if (b & 1) > 0:
result = mod_mul(result, a, n)
a = mod_mul(a, a, n)
b = (b >> 1)
return result
def MillerRabinPrimeCheck(n):
if n in {2, 3, 5, 7, 11}:
return True
elif (n == 1 or n % 2 == 0 or n % 3 == 0 or n % 5 == 0 or n % 7 == 0 or n % 11 == 0):
return False
k, u = 0, n - 1
while not (u & 1) > 0:
k += 1
u = (u >> 1)
random.seed(0)
s = 5
for i in range(s):
x = random.randint(2, n - 1)
if x % n == 0:
continue
x = mod_exp(x, u, n)
pre = x
for j in range(k):
x = mod_mul(x, x, n)
if (x == 1 and pre != 1 and pre != n - 1):
return False
pre = x
if x != 1:
return False
return True
def Pollard_rho(x, c):
(i, k) = (1, 2)
x0 = random.randint(0, x)
y = x0
while 1:
i += 1
x0 = (mod_mul(x0, x0, x) + c) % x
d = gcd(y - x0, x)
if d != 1 and d != x:
return d
if y == x0:
return x
if i == k:
y = x0
k += k
def PrimeFactorsListGenerator(n):
result = []
if n <= 1:
return None
if MillerRabinPrimeCheck(n):
return [n]
p = n
while p >= n:
p = Pollard_rho(p, random.randint(1, n - 1))
result.extend(PrimeFactorsListGenerator(p))
result.extend(PrimeFactorsListGenerator(n // p))
return result
def PrimeFactorsListCleaner(n):
return Counter(PrimeFactorsListGenerator(n))
PrimeFactorsListCleaner(1254000000)
到了这里,关于Python:分解质因数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!