欧拉计划-合数的最大质因子-求解惑
我的方案是#计算一个合数的最大质因子
import time
number = int(input('请输入要求最大质因子的数字:'))
start = time.clock()
def prime(param):
'判断是否是质数'
if param < 3:
return 1
for i in range(3,param-1):
if param%i == 0:
return 0
return 1
'''质因子从该数字number的中间处开始判断
-只判断奇数数字 每次递减2
-先判断是因子、再判断是质数
-满足条件即是所需的最大质因子
'''
factor = number // 2
if factor%2 ==0:
factor = factor + 1
while 1:
if number%factor ==0:
if prime(factor):
print('%d的最大质因子是%d'%(number, factor))
break
factor -= 2
end = time.clock()
print('耗时：%f'%(end - start))
--计算9位数耗时就有3s
--看了其他鱼友的代码发现他们先对合数进行开方，在平方根的范围内判断
求解为什么要先开方。。。。。。。。。 本帖最后由 ba21 于 2017-8-4 17:29 编辑
假设：
请输入要求最大质因子的数字: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 17:28 编辑
运维小书童 发表于 2017-8-4 16:39
感谢版主的回答！
那如果要判断的数字是:95
95的最大质因子是 :19
查了下资料：
因为如果一个数不是素数是合数，
那么一定可以由两个自然数相乘得到，
其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。
所以 开出来的根 得到的是一个小于或等于它的平方根的数 然后根据这个计算出最大质因子
页:
[1]