Ruby中数字的最大素数因子

Question

早上好,

我编写了以下代码,它与小数字一起使用,以找到数字的最大主要因素.我无法使用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)系统的边缘情况冻结.

任何人都可以告诉我如何重构我的代码,使其更有效率？

非常感谢!

Answer 1

您的代码存在许多问题,导致其效率非常低:

• 在您的biggest_prime方法中,您Array在内存中构造一个小于目标数的每个数字,而不是仅仅迭代该范围.因为600851475143,Array内存中的大小约为4 TiByte.你有4 TiByte的RAM吗？如果没有,您的系统将创建一个巨大的交换文件并不断交换.用一个Range代替!事实上,你已经在使用a了Range,但是Array根本没有任何理由将它转换为.
• 您的is_prime?方法也会发生同样的情况.这Array是一个小得多(最大只有大约6 MiByte),但你一遍又一遍地创造它6000 亿次!创建Arrayn个数字需要花费O(n)个时间,因此创建一个Arrayn次的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年.

所以,你需要做的是大量减少迭代次数和内存量.

后者最简单:使用Ranges而不是Arrays.

前者需要一点思考.这是一个想法:你一遍又一遍地检查相同的数字.这不是必要的.一旦你确定一个数字是一个除数,你已经知道它是一个除数,你不需要再检查它.

同样,您反复检查相同的数字以获得素数.但是一旦你确定一个数字是素数,你就不需要再次检查,毕竟它不太可能改变.

但首先,让我们看看最有效的解决方案是什么样的:

require 'prime'

def biggest_prime(number)
  number.prime_division.last.first
end