题目：

每日一练（2-26）：
题目：将一个整数分解质因数。例如：输入90,打印出90=2*3*3*5

实现方法：

百度百科里对分解质因数的定义：
把一个合数分解成若干个质因数的乘积的形式，即求质因数的过程叫做分解质因数。
分解质因数只针对合数。（分解质因数也称分解素因数）求一个数分解质因数，要从最小的质数除起，一直除到结果为质数为止。分解质因数的算式叫短除法，和除法的性质相似，还可以用来求多个数的公因式。
只需要用while for循环即可解决，适合新手入门python进行练习，本文将由易到难介绍几种实现思路，并附上代码和所需要的知识点。

参考答案

思路：暴力算法，死循环计算，缺点：耗时

# 学习交流请来Python学习群：922624810【或加个人WX: felix107ye 】
num = 90

def gongyz(num):
	for i in range (2,num):
		if num % i == 0:
			print(i)
			return gongyz(num//i)
	print(num)
gongyz(num)
1
2
3
4
5
6
7
8
9
10

输出：

2
3
3
5
[Finished in 0.2s]
1
2
3
4
5

其他思路参考答案

思路1：首先设置函数判断是否是质数，然后依次进行分解

# -*- coding: utf-8 -*-
# @Time    : 2020年2月27日
# @Software: PyCharm
# from Python学习交流群：922624810

#判断数据是否是质数，用于保证大整数分解时每一个因子都是质数
def zhishu(num):
    for i in range(2,num):
        if num % i == 0:
            #print('%d 是个合数，可以分解' %num)
            return True
            #break 楼主之前一个版本加了break，忽略了函数return之后其他语句不会执行，相当于break了。
    else:#和for对齐，是python独有的语法如果for循环里的语句执行结束后执行else语句，如果for循环里有break则else后的语句不会执行。
        #print('%d 是个质数，请输入1个合数' %num)
        return False

def zhiyinshufenjie(num):
    nump = num#用于输出 90 = 2*3*3*5
    tmp = []
    if not zhishu(num):
         print('%num是个质数，请输入一个合数')#如果是质数则不用执行语句
    else:
        while num:#用于控制循环次数直到为0
            if not zhishu(num) and num != 1:#排除1，因为1在分解中没有意义
                tmp.append(num)
                num = 0
            else:
                for i in range(2, int(num**(1/2))+1):#num**(1/2)为了缩短计算范围，在计算超大数时有用
                    if num % i == 0 & (not zhishu(i)):
                        tmp.append(i)
                        num = int(num/i) 
                        #print(i)
                        break         
                #print(num) 
    tmp = sorted(tmp)#排成有序数组
	#设置打印格式    
	str1 = ''
    for i in range(len(tmp)):
        if i== 0:
            str1= str1 + str(tmp[i])
        else:
            str1= str1 + '*' +str(tmp[i])
    returnstr = '%d = %s' % (nump,str1)
    return returnstr
numz = int(input("请输入一个正整数： "))
a=zhiyinshufenjie(numz)
print(a)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

结果输出：

请输入一个正整数： 2345
2345 = 5*7*67

Process finished with exit code 0
1
2
3
4

思路2：优化求解法，是在第一种思路下进行优化
第二种思路区别于第一种思路在于，第一个被整除的数永远是质数，比如1，2，3，5，7，如果是4和6那么也能被2整除。此时只需要不断更新被除后的数，就能计算出最终的质因数。此处还有几个小技巧，如保持除完以后还是整数，用//，在同一行打印，则设置print的参数为end=’’。

def fenjiezhiyinshu(num):
    n = num 
    f = []
    for j in range(1,num//2+1):
        for i in range(2, n):
            if n % i == 0:
                f.append(i)
                n = n//i
                break
    if len(f) == 0:
        print("这是一个质数，请重新带入合数")
    else:
        f.append(n)
        f.sort()
        print('%d=%d'% (num,f[0]), end='')
        for i in range(1,len(f)):
            print('*%d'%f[i] ,end='') 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

百度百科的解法

# 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)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

参考文档：
1、#作者：不分享的知识毫无意义
#链接：https://www.jianshu.com/p/d37745fe3cdd
#来源：简书
2、#百度百科： https://baike.baidu.com/item/%E5%88%86%E8%A7%A3%E8%B4%A8%E5%9B%A0%E6%95%B0
1
2
3
4
5