找到> 500因子的第一个三角形数字的算法运行缓慢

这是我的算法，它找到带有> x因子的第一个三角形数字。 我可以把它运行到大约x = 150，然后它需要永远。 我可以做些什么改变来加快速度？ 谢谢！

def triangle_numbers_max_divisors(x) triangle_numbers = [] divisors = 0 a = 1; b = 2 until divisors > x divisors = 0 triangle_numbers.push(a) a = a + b; b += 1 for i in 1..triangle_numbers.last if triangle_numbers.last % i == 0 divisors += 1 end end end triangle_numbers.last end 

Answer 1

代码运行缓慢的原因已在其他答案中给出。 这是一种类似Ruby的编码算法的方法。 大约需要10秒才能解决。*

码

 def triangle_numbers_max_divisors(min_nbr_factors) (1..Float::INFINITY).reduce(0) do |tnbr, n| tnbr += n return tnbr if nbr_factors(tnbr) >= min_nbr_factors tnbr end end def nbr_factors(n) m = Math.sqrt(n) 2 * 1.upto(m).count { |i| (n % i).zero? } - ((n == m * m) ? 1 : 0) end p triangle_numbers_max_divisors(500) #=> 76_576_500 

说明

• 您只需要一个值，因此无需保留除数。 算一算吧。
• 如果n是一个完美的平方，则术语- ((n == m * m) ? 1 : 0使n的平方根只计算一次。
• 有时您会看到(1..Float::INFINITY)写为(1..1.0/0) 。

。 *在最近的老式Macbook Pro上

Answer 2

看起来你正在尝试解决项目Euler的问题编号12，称为Highly divisible triangle number 。

我试图改进你的代码，但遗憾的是你的解决方案本身速度慢且效率低，如果不改变方法就不能从根本上改进。 看看这个解决方案 ，也看看这个SO 线程 。

Answer 3

我不知道这是否是最新的，但是重新为数组重新分配空间似乎存在问题。 在127处，您的代码仅需要大约6秒钟运行，然后在128处跳转到30秒。它会再次关闭一段时间。

如果你使用类似triangle_numbers = Array.new(x)类的东西预先分配数组，你将失去简洁的.last语法，并且必须跟踪数组索引，但代码在整个电路板上以大致的二次方运行。 这意味着它每次增加的速度仍会不成比例地变慢，但是你可以做的并不多，你不应该碰到任何奇怪的不连续性。