最大质因数算法优化

ietar

p3为原算法 p3_mix为优化后算法 开头的timef为手写计时小轮子

原算法思路 从小到大取约数n 尝试整除原数a 整除成功则令a=a/n 循环直到a为质数 此时a为原数的最大质因数

p3_mix 优化了取余数的过程 记录上次取到的余数n 每次循环从n开始从小到大取约数 并只取质数（合数均可表示为质数乘积）

p3_get_prime(n)只简单用了质数的通项公式 并未对n进行检测 因此返回值中带有不合要求的合数 好在也含有全部质数 就是每一跳步子不够大

(哪怕来个质数的迭代公式也好啊)


在一些情况下 mix算法效率明显高于原算法
比如 60085147514 （原题600851475143 去掉了最后的3）

half_failed_fix

取约数时保存上次循环进度 不考虑质数的p3_softfix()

soft_fix

1. import time
   
2. 
   
3. def timef(function,number=1000):
   
4.         t1=time.perf_counter()
   
5.         for i in range(number):
   
6.                 function
   
7.         t2=time.perf_counter()
   
8.         return t2-t1
   
9. 
   
10. def p3(a = 600851475143):
    
11.     import math
    
12.     def p3_get_prime(n):
    
13.         return int(3*n+1+(math.sin(math.pi*n/2))**2)
    
14. 
    
15.     def is_prime(n):
    
16.         if not n%2:
    
17.             return False
    
18.         n1 = int(math.sqrt(n))
    
19.         for i in range(3,n1+1,2):
    
20.             if not n%i:
    
21.                 return False
    
22.         return True
    
23.    
    
24.     # 肉眼可见2不是a的约数
    
25.     def p3_1(n,num=1):
    
26.         if is_prime(n):
    
27.             return n
    
28.         for i in range(3,a//3+1):
    
29.             if not n%i:
    
30.                 return p3_1(n/i)
    
31.     return (p3_1(a))
    
32.    
    
33. def p3_softfix(a = 600851475143):
    
34.     import math
    
35.     def p3_get_prime(n):
    
36.         return int(3*n+1+(math.sin(math.pi*n/2))**2)
    
37. 
    
38.     def is_prime(n):
    
39.         if not n%2:
    
40.             return False
    
41.         n1 = int(math.sqrt(n))
    
42.         for i in range(3,n1+1,2):
    
43.             if not n%i:
    
44.                 return False
    
45.         return True
    
46.    
    
47.     # 肉眼可见2不是a的约数
    
48.     def p3_1(n,num=2):
    
49.         if is_prime(n):
    
50.             return n
    
51.         for i in range(num,int(n//3)+1):
    
52.             if not n%i:
    
53.                 num = i
    
54.                 return p3_1(n/i,num)
    
55.     return p3_1(a)
    
56. 
    
57. 
    
58. def p3_mix(a = 600851475143):
    
59.     import math
    
60.     def p3_get_prime(n):
    
61.         #产生的并不仅是质数 但包含所有质数 just ok
    
62.         return int(3*n+1+(math.sin(math.pi*n/2))**2)
    
63. 
    
64.     def is_prime(n):
    
65.         if not n%2:
    
66.             return False
    
67.         n1 = int(math.sqrt(n))
    
68.         for i in range(3,int(n//3)+1):
    
69.             if not n%i:
    
70.                 return False
    
71.         return True
    
72.    
    
73.     def p3_1_mix(n,num=1,i=2):
    
74.         if is_prime(n):
    
75.             return n
    
76.         while i < n//2+1:
    
77.             if not n%i:  # n被i整除
    
78.                 return p3_1_mix(n/i,num,i)
    
79.             else:  # n无法被i整除
    
80.                 if i == 2:
    
81.                     i = 3
    
82.                 elif i == 3:
    
83.                     i = p3_get_prime(num)
    
84.                 else:
    
85.                     num += 1
    
86.                     i=p3_get_prime(num)
    
87.     return (p3_1_mix(a))
    
88.                
    

复制代码