1

Ruby を使用して問題を解決する練習をするために、Project Euler の問題をいくつか見ていきます。私は問題 3 に対して次の解決策を思いつきました。これは小さい数値では機能しますが、大きい数値に対しては決して値を返さないようです。これはBignumと関係があるためですか？タイムアウトの理由と、この問題を解決するためのより良い方法を誰かが私に説明できますか (できれば、舞台裏で何が起こっているかについての推論/情報を使用してください。私は理解しようとしています)

プロジェクト オイラー問題:

13195 の素因数は 5、7、13、29 です。600851475143 の最大の素因数は?

私の解決策：

def primecheck(number)
  (2...number).each { |x| return false if number % x == 0}
  true
end

def largestprime(number1)
  factors = []
    (1..number1).each do |i|
      if number1 % i == 0 && primecheck(i)
        factors << i
      end
    end
puts "The answer is #{factors.last}"
end

largestprime(600_851_475_143)
4

2 に答える 2

10

ヒント:素因数が見つかったら、それで割ることができます。これにより、チェックしなければならない残りの潜在的な除数の範囲が大幅に縮小されます。

あなたの最初の例を使用して：

13195/5 = 2639,
2639/7  = 377,
377/13  = 29,
29/29   = 1, done.

この方法では、13195 までではなく、29 までチェックするだけで済みました。

さらに改善する方法はありますが、この単純な問題には、この最適化だけで十分です。

于 2013-05-10T02:58:39.530 に答える
4

1 から 600851475143 までのすべての数字を調べています。また、すべての数字について、数字が素数かどうかもチェックします。したがって、操作の総数は O(n^3/2) で、約 10^18 になるはずです。それを計算するには何年もかかると予想されます。漸近的な複雑さが軽減されるようにアルゴリズムを変更する必要があります

于 2013-05-10T02:46:19.763 に答える