首页 文章

试图找到最大的素因子

提问于
浏览
0

这来自Euler项目的第3个问题:

https://projecteuler.net/problem=3

问题:13195的主要因素是5,7,13和29. 600851475143中最大的素数因子是什么?

因为这是一个难题,我宁愿不使用 jar 装Ruby方法 . 所以这里......

当前逻辑:
num是我们正在寻找的素数因子 .
候选人是潜在的主要因素
sqrt是num的平方根

until candidate >= sqrt

我从Eratosthenes的Sieves借用了这个想法来寻找素数,其中算法检查每个数字的可除性,直到num的平方根 . 候选是要测试num是否有除数的数字 .

if num % candidate == 0
...
end

目标是检查num是否可以被任何东西整除(有因子) . 如果num不能被候选者整除,则候选者将递增1直到 until 语句为真或者直到num可被候选者整除 .

如果num可以被候选者整除,那么我们知道候选者是素数并且它被插入到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

1 回答

  • 0

    所以看起来,正如你所建议的,问题是递归逻辑 .

    仅仅因为你递归地调用函数并不意味着“父”停止工作 - 他只是坐着等待“孩子”完成,然后继续前进 . 这就是“过度循环”发生的地方 . 代码实际上并没有过度循环,而是完成了 .

    你可以在puts语句中看到这一点 . 请注意,在循环停止后,sqrt会增加,因为脚本现在正在运行父代码,而不是在递归的片段(子代)完成之后 .

    对于修复,我做了两件事: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
    

相关问题