我正在研究一些欧拉项目问题来练习使用 Ruby 解决问题。我针对问题 3 提出了以下解决方案,虽然它适用于较小的数字,但它似乎永远不会返回较大数字的值。这是因为与 Bignum 有关吗?有人可以向我描述为什么它超时了,以及解决这个问题的更好方法(最好是关于幕后发生的事情的推理/信息。我正在尝试理解)
欧拉计划问题:
13195 的质因数是 5、7、13 和 29。
数字 600851475143 的最大质因数是多少?
我的解决方案:
def primecheck(number)
(2...number).each { |x| return false if number % x == 0}
true
end
def largestprime(number1)
factors = []
(1..number1).each do |i|
if number1 % i == 0 && primecheck(i)
factors << i
end
end
puts "The answer is #{factors.last}"
end
largestprime(600_851_475_143)
Hint:一旦找到素因数,就可以除以它。这大大减少了您必须检查的剩余潜在除数的范围。
使用你的第一个例子:
13195/5 = 2639,
2639/7 = 377,
377/13 = 29,
29/29 = 1, done.
这样,我们只需检查最多 29 个,而不是一直检查到 13195。
有一些方法可以进一步改进它,但仅此优化就足以解决这个简单的问题。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)