试图找到最大的质因数

Question

这来自欧拉计划的第 3 个问题。:

问题： 13195 的质因数是 5、7、13 和 29。 600851475143这个数的最大质因数是多少？

因为这是一个谜题，所以我不想使用固定的 Ruby 方法。所以就这样...

当前逻辑：
num 是我们要寻找质因数的数字。
候选人是一个潜在的主要因素
sqrt 是 num

的平方根

until candidate >= sqrt

我从 Eratosthenes 的 Sieves 那里借用了这个想法来寻找素数，其中算法检查每个数字的整除性直到 num 的平方根。 candidate 是测试 num 是否有除数的数字。

if num % candidate == 0
...
end

目标是检查 num 是否可以被任何东西整除（有因数）。如果 num 不能被 candidate 整除，那么 candidate 将递增 1，直到 until 语句为真或直到 num 可以被 candidate 整除。

如果 num 可以被 candidate 整除，那么我们就知道 candidate 是质数并且它被插入到 prime_factor 中。然后递归正好测试新定义的num.

prime_factors << num

如果 until 循环为真，则该 num 没有除数，因此是质数。结果，它被插入 prime_factors.

问题：

问题不在于它超时，而在于它给出了错误的答案。看来我的代码循环次数超出了需要。我向其中添加了一些日志记录。我不确定为什么，但我认为它与递归部分有关。诚然，我从不在我的代码中使用递归，而是想用它来扩展我的技能。所以从概念上讲，递归对我来说一般是模糊的。任何阅读也会有所帮助。

应该发生什么：
prime_factors = [2,2,19]
prime_factors.last = 19

实际发生了什么：
prime_factors = [2,2,19,19,38]
prime_factors.last = 38

全部代码：

def largest_prime_factor(num,prime_factors)
 puts "beg fx: num: #{num},  prime_factors: #{prime_factors}
 candidate = 2
 sqrt = Math.sqrt(num)
 loop_count = 0
 until candidate >= sqrt
   if num % candidate == 0
     num = num / candidate
     prime_factors << candidate
     largest_prime_factor(num,prime_factors)
   end
   candidate += 1
   loop_count +=1
 end
   puts "outside loop: candidate >= sqrt is #{candidate >= sqrt} num: #{num}, prime_factors: #{prime_factors}, candidate: #{candidate}, sqrt: #{sqrt}, loop: #{loop_count}" 
   gets
 prime_factors << num
 prime_factors.last
end

Answer 1

看来，正如您所建议的，问题出在递归逻辑上。

仅仅因为你递归地调用一个函数并不意味着 "parent" 停止工作 - 他只是坐着等待 "child" 完成，然后继续前进。这就是 "over looping" 发生的地方。代码实际上并没有过度循环，而是结束了。

您可以在您的 puts 语句中看到这一点。请注意，在循环停止后，sqrt 增加，因为脚本现在运行ning 父代码，而不是在递归片段（子）完成之后。

为了修复，我做了两件事： 1. 创建一个布尔值，表示代码块已经递归。如果是这样，运行这段代码，否则... 运行其他。 2. 如果候选不是 2，则递增 2。这将跳过测试除 2 之外的所有偶数。无需测试其他偶数，因为它不是质数。

def largest_prime_factor(num,prime_factors,recursive)
  candidate = 2
  until candidate >= Math.sqrt(num)
    recursive = false
    if num % candidate == 0
      num = num / candidate
      recursive = true
      prime_factors << candidate
      largest_prime_factor(num,prime_factors,recursive)
    end
    break if recursive
    candidate == 2 ? candidate += 1 : candidate += 2
  end
  prime_factors << num unless recursive
  prime_factors.last
end

试图找到最大的质因数

Trying to find largest prime factor

ruby

prime-factoring