[已解决]欧拉计划-合数的最大质因子-求解惑

运维小书童

我的方案是

1. #计算一个合数的最大质因子
   
2. import time
   
3. 
   
4. number = int(input('请输入要求最大质因子的数字:'))
   
5. start = time.clock()
   
6. 
   
7. def prime(param):
   
8.     '判断是否是质数'
   
9.     if param < 3:
   
10.         return 1
    
11.     for i in range(3,param-1):
    
12.         if param%i == 0:
    
13.             return 0
    
14.     return 1
    
15. 
    
16. '''质因子从该数字number的中间处开始判断
    
17.     -只判断奇数数字 每次递减2
    
18.     -先判断是因子、再判断是质数
    
19.     -满足条件即是所需的最大质因子
    
20. '''
    
21. factor = number // 2
    
22. if factor%2 ==0:
    
23.     factor = factor + 1
    
24. while 1:
    
25.     if number%factor ==0:
    
26.         if prime(factor):
    
27.             print('%d的最大质因子是%d'%(number, factor))
    
28.             break
    
29.     factor -= 2
    
30. 
    
31. 
    
32. end = time.clock()
    
33. print('耗时：%f'%(end - start))

复制代码

--计算9位数耗时就有3s
--看了其他鱼友的代码发现他们先对合数进行开方，在平方根的范围内判断
求解为什么要先开方。。。。。。。。。

最佳答案

月排行榜 / 总排行榜

ba21

2017-8-4 17:22:37

运维小书童 发表于 2017-8-4 16:39
感谢版主的回答！
那如果要判断的数字是:95
95的最大质因子是 :19

查了下资料：
因为如果一个数不是素数是合数，
那么一定可以由两个自然数相乘得到，
其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。

所以 开出来的根 得到的是一个小于或等于它的平方根的数 然后根据这个计算出最大质因子

跳转到最佳答案楼层

ba21

假设：

请输入要求最大质因子的数字:99
99的最大质因子是11
---------------------------------------------
11 * 11 =121要比99大了。先开方就能最快的判断出最大质因子数。 得到的是一个小于或等于它的平方根的数 然后根据这个计算出最大质因子
====================================================
请输入要求最大质因子的数字:98
98的最大质因子是7（2*7*7 = 98）
-----------------------------------------------------
98开方后约为10， 10*10=100 比98大了。 得到的是一个小于或等于它的平方根的数 然后根据这个计算出最大质因子

运维小书童

ba21 发表于 2017-8-4 15:33
假设：

请输入要求最大质因子的数字:99

感谢版主的回答！
那如果要判断的数字是:95
95的最大质因子是 :19
19就要比95的平方根大了 这种情况就出错了。
还是判断的数字有什么特殊情况需要考虑吗？

冬雪雪冬

运维小书童 发表于 2017-8-4 16:39
感谢版主的回答！
那如果要判断的数字是:95
95的最大质因子是 :19

应该这样理解，如果没有平方根之内的因子，就不可以有更大的因子。以95为例，如果没有10以内的因子5，就不可能有19.所以判断到平方根就可以了。

ba21

运维小书童 发表于 2017-8-4 16:39
感谢版主的回答！
那如果要判断的数字是:95
95的最大质因子是 :19

查了下资料：
因为如果一个数不是素数是合数，
那么一定可以由两个自然数相乘得到，
其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。

所以 开出来的根 得到的是一个小于或等于它的平方根的数 然后根据这个计算出最大质因子