作者:用户tkeex06qp1 | 来源:互联网 | 2022-12-09 12:56
早上好,
我编写了以下代码,它与小数字一起使用,以找到数字的最大主要因素.我无法使用Prime
,我需要提出一个手动解决方案.
def is_prime?(number)
list = (2..(Math.sqrt(number))).to_a
list.each do |i|
return false if number % i == 0
end
true
end
def biggest_prime(number)
list = (2..((number))).to_a
divisors = list.select{|i| is_prime?(i)}
divisors.select{|i| number % i == 0 }.max
end
13195的主要因素是5,7,13和29.
biggest_prime(13195) => 29
但是,当我尝试biggest_prime(600851475143)
系统的边缘情况冻结.
任何人都可以告诉我如何重构我的代码,使其更有效率?
非常感谢!
1> Jörg W Mitta..:
您的代码存在许多问题,导致其效率非常低:
在您的biggest_prime
方法中,您Array
在内存中构造一个小于目标数的每个数字,而不是仅仅迭代该范围.因为600851475143
,Array
内存中的大小约为4 TiByte.你有4 TiByte的RAM吗?如果没有,您的系统将创建一个巨大的交换文件并不断交换.用一个Range
代替!事实上,你已经在使用a了Range
,但是Array
根本没有任何理由将它转换为.
您的is_prime?
方法也会发生同样的情况.这Array
是一个小得多(最大只有大约6 MiByte),但你一遍又一遍地创造它6000 亿次!创建Array
n个数字需要花费O(n)个时间,因此创建一个Array
n次的sqrt(n)个数需要O(n*sqrt(n))时间.总的来说,您需要SUM(sqrt(n),n = 1 TO 600851475143)步骤,这大约是310498000000000000步.
这也是整个算法所需的步骤数.甚至如果你有一个10 GHz的CPU,而该CPU有100个核心,而你的问题是完全并行的,并且你可以在单个CPU指令中执行你的算法的一个完整迭代,你仍然需要3.5天得到的结果.由于您没有使用并行性,可能没有10 GHz CPU,并且迭代将花费10或数百个CPU周期,更实际的数字将至少为100年.
所以,你需要做的是大量减少迭代次数和内存量.
后者最简单:使用Range
s而不是Array
s.
前者需要一点思考.这是一个想法:你一遍又一遍地检查相同的数字.这不是必要的.一旦你确定一个数字是一个除数,你已经知道它是一个除数,你不需要再检查它.
同样,您反复检查相同的数字以获得素数.但是一旦你确定一个数字是素数,你就不需要再次检查,毕竟它不太可能改变.
但首先,让我们看看最有效的解决方案是什么样的:
require 'prime'
def biggest_prime(number)
number.prime_division.last.first
end
@Sergi也许你可以在问题中指明它!
或者也许在文档中查看"prime"的来源.它用Ruby编写.