题目描述
将n阶乘分解质因式
样例
10
2 8
3 4
5 2
7 1
算法1
(素数筛法)
python3 代码
n=int(input())
isPrime=[True](n+1)
fixPrime=[0](n+1)
for i in range(2,n+1):
if isPrime[i]:
fixPrime[i]+=1
for j in range(i+i,n+1,i):
isPrime[j]=False
else:
while True:
if isPrime[i]:
fixPrime[i]+=1
break
else:
for j in range(2,i):
if isPrime[j] and i%j==0:
fixPrime[j]+=1
i=i//j
break
for i in range(2,n+1):
if fixPrime[i]:
print(i,fixPrime[i])
算法2
(6n±1筛选法)
python3 代码
’‘’
任何一个自然数,总可以表示成以下六种形式之一:
6n,6n+1,6n+2,6n+3,6n+4,6n+5
我们可以发现,除了2和3,只有形如6n+1和6n+5的数有可能是质数。
且形如6n+1和6n+5的数如果不是质数,
它们的因数也会含有形如6n+1或者6n+5的数
而且最小的因数必定为素数
‘’‘
def minPrime(n): #可用i==minPrime(i)判断素数
x=n%6 #或修改返回值判断素数
if x in [0,2,4]:
return 2
elif x in [3]:
return 3
elif x in [1,5]: #6n±1
for i in range(5,int(n**0.5)+1,6):
if n%i==0:
return i
if n%(i+2)==0: #i或i+2也是素数
return i+2
return n
n=int(input())
fixPrime=[0]*(n+1)
for i in range(2,n+1):
while i!=1:
x=minPrime(i)
fixPrime[x]+=1
i=i//x
for i in range(2,n+1):
if fixPrime[i]:
print(i,fixPrime[i])