蓝桥杯 Python 练习题 分解质因数

蓝桥杯 Python 练习题 分解质因数

题目 1464: 蓝桥杯基础练习VIP-分解质因数

时间限制: 1Sec 内存限制: 128MB 提交: 3835 解决: 2257

题目描述

求出区间[a,b]中所有整数的质因数分解。

提示
先筛出所有素数，然后再分解。

数据规模和约定

输入

输入两个整数a，b。 

2< =a< =b< =10000

输出

每行输出一个数的分解，形如k=a1*a2*a3...(a1< =a2< =a3...，k也是从小到大的)(具体可看样例) 

样例输入复制

3 10

样例输出复制

3=3
4=2*2
5=5
6=2*3
7=7
8=2*2*2
9=3*3
10=2*5

---

 分解质因数：把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。

def fj(a,b):
    for i in range(a,b+1):
        jilu=[]
        n=i
        while True:
            for j in zs:
                if(n%j==0):
                    jilu.append(j)
                    break
            if(n//j==1):
                    break
            n=n//j
        zhiy='*'.join(map(str,jilu))
        #把列表中的元素转化为字符串，然后转化成一个用*分割的一整个字符串
        print("{}={}".format(i,zhiy))
        
zs=[2]
for i in range(3,10001):#创建质数列表
    for j in range(2,i//2+2):
        if(i%j==0):
            break
    if(j==i//2+1):
        zs.append(i)

a,b=map(int,input().split())
fj(a,b)