用python写的分解质因数的程序（对速度进行了一定的优化）

rqwqlnjrsf

自己写了一个用于分解质因数的程序，优化了一下速度，使16位以内的数的分解速度，限制在几百毫秒以内

1. import time as t
   
2. 
   
3. def prime_factorization(i):
   
4.     i = int(i)
   
5.     t1 = t.time()
   
6.     x = []
   
7.     y = []
   
8.     p = i
   
9.     j = 2
   
10.     heshu = False
    
11.     while i != 1.0 and j <= i:
    
12.         if i % j == 0:
    
13.             heshu = True
    
14.         if heshu == True and j > i ** 0.5:
    
15.             x.append(int(i))
    
16.             y.append(1)
    
17.             break
    
18.         
    
19.         if i % j != 0:
    
20.             j += 1
    
21.             if j > p ** 0.5 and heshu == False:
    
22.                 print('\n\t您输入的数字是质数！', end='')
    
23.                 break
    
24.             continue
    
25.             
    
26.         count = 0
    
27.         x.append(j)
    
28.         while i % j == 0:
    
29.                 count += 1
    
30.                 i /= j
    
31.                
    
32.         y.append(count)
    
33.         #print(i, i ** 0.5)
    
34. 
    
35.     if heshu == True:
    
36.         print('\n\t质因数分解： '+str(p)+' = ', end='')
    
37.         for m in range(len(y)):
    
38.             print(str(x[m])+'^'+str(y[m]), end='')
    
39.             if m < len(y) - 1:
    
40.                 print(' * ', end='')
    
41.     t2 = t.time()
    
42.     deltat = round(t2 - t1, 3)
    
43.     print()
    
44.     print('\t跑完程序所花时间： '+str(deltat)+' 秒。\n')
    
45. 
    
46. while True:
    
47.     i = input('请输入要分解的正整数：')
    
48.     try:
    
49.         i = int(i)
    
50.     except ValueError:
    
51.         print('您输入的不是数，请重新输入！')
    
52.         continue
    
53.     if int(i) < 0:
    
54.         i *= -1
    
55.     prime_factorization(i)
    
56.         
    
57.    

复制代码

运行结果见截图