求一个数的最小素数因子序列

**

求一个数的最小素数因子序列

**

---

• 如 120 = 22235，其中2， 2，2，3，5就是120 的最小素数因子 90 = 233*5
  ，其中2，3，3，5 就是90 的最小素数因子

---

具体思路是：

1. 计算出该数字的所有质数因子

def isPrime(n):  #判断一个大于1的整数是否是素数，返回值为True和False
    isprime = True
    for i in range(2,n):
        if n % i == 0:
            isprime = False
            break
    return  isprime

lsPrimeDivisor = [ ]  #所有素数因子列表
for i in range(2,num//2+1):
    if num%i==0 and isPrime(i):
        lsPrimeDivisor.append(i)

2.使用连续除法方法，求出最小素数因子序列，以120为例：
3.主函数：

#以下为主函数
num = eval(input("输入一个整数："))

lsPrimeDivisor = [ ]  #所有素数因子列表
for i in range(2,num//2+1):
    if num%i==0 and isPrime(i):
        lsPrimeDivisor.append(i)

print(lsPrimeDivisor[0], end="")  #逗号间隔思路，先提前打印一个不换行
num = num / lsPrimeDivisor[0]
i = 0
while i<len(lsPrimeDivisor):  #打印所有最小因子
    if num % lsPrimeDivisor[i] == 0:  #判断最小素数因子
        print(",",lsPrimeDivisor[i], end = "")  #先打逗号后打值
        num = num / lsPrimeDivisor[i]  #当除数能被当前素数因子整除时，求其整除的商作为下次迭代的除数
        #print(num)
    else:  #当商不能被当前素数因子整除时，换下个素数因子
        i += 1

4.完整代码

def isPrime(n):  #判断一个大于1的整数是否是素数，返回值为True和False
    isprime = True
    for i in range(2,n):
        if n % i == 0:
            isprime = False
            break
    return  isprime

#以下为主函数
num = eval(input("输入一个整数："))

lsPrimeDivisor = [ ]  #所有素数因子列表
for i in range(2,num//2+1):
    if num%i==0 and isPrime(i):
        lsPrimeDivisor.append(i)

print(lsPrimeDivisor[0], end="")  #逗号间隔思路，先提前打印一个不换行
num = num / lsPrimeDivisor[0]
i = 0
while i<len(lsPrimeDivisor):  #打印所有最小因子
    if num % lsPrimeDivisor[i] == 0:  #判断最小素数因子
        print(",",lsPrimeDivisor[i], end = "")  #先打逗号后打值
        num = num / lsPrimeDivisor[i]  #当除数能被当前素数因子整除时，求其整除的商作为下次迭代的除数
        #print(num)
    else:  #当商不能被当前素数因子整除时，换下个素数因子
        i += 1

5.课后答案：

# Prompt the user to enter a positive integer
number = eval(input("Enter a positive integer: "))
    
# Find all the smallest factors of the integer
print("The factors for " + str(number) + " is ", end = "")
factor = 2
while factor <= number:
    if number % factor == 0:
        number = number / factor
        print(factor, end = " ")
    else:
        factor += 1

6.总结：
解题思路很重要