1

これは、プロジェクトのオイラー問題の 1 つに対する (かなり悪い) 解決策です。問題は、10_001 番目の素数を見つけることでした。以下のコードで実行できますが、実行に 8 分かかります。その理由と、それを最適化する方法を説明できますか?

primes = []
number = 2.0

until primes[10000] != nil
  if (2..(number - 1)).any? do |n|
    number % n == 0
  end == false
    primes << number
  end
  number = number + 1.0
end

puts primes[10000]
4

2 に答える 2

7

発見をプライムするためのいくつかの簡単な最適化：

  • 2を素数リストにプッシュすることから始め、3が素数であるかどうかを確認することから始めます。（これにより、0から2までの数字に特別な場合のコードを記述する必要がなくなります）

  • あなたはプライム候補のために奇妙な数をチェックする必要があるだけです。（または、2/3/5を追加して7をチェックすることから始める場合は、％6を実行した後に1または5の数値をチェックするだけで済みます。または...あなたはアイデアを得る）

  • 現在の候補がsqrt（ ）xまでの因数で割り切れるかどうかを確認するだけで済みます。これは、上の因数がxを下の数に分割し、それらすべてをすでにチェックしているためです。xsqrt(x)sqrt(x)

  • xすべての合成数は素数で割り切れるので、-の約数については、すべての数ではなく、素数リストの数をチェックするだけで済みます。たとえば、81は9 * 9ですが、9*9は3*3 * 9であり、9は合成であるため、3と照合すると素数であることがわかります。したがって、9が因子であるかどうかをテストする必要はありません。 、など、すべての複合因子について。

非常に最適化された高速化された素数検索関数があります（開始についてはアトキンのふるいを参照）が、これらは簡単に思い付くことができる一般的な最適化です。

于 2013-03-18T00:17:30.600 に答える
1

数字が以前のすべての数字で割れるかどうかを本当に確認する必要がありますか？すでに発見した小さい素数でのみ確認してください。また、整数が完全に細かい場所でフロートを使用するのはなぜですか？

編集：

いくつかの可能な変更（最良のアルゴリズムではない、改善できる）：

primes = [2, 3, 5]
num = 7

until primes[10000]
  is_prime = true
  i = 0
  sqrtnum = Math.sqrt(num).ceil
  while (n=primes[i+=1]) <= sqrtnum
    if num % n == 0
      is_prime = false
      break
    end
  end
  if is_prime
    primes << num
  end
  num += 2
end

puts primes[10000]

私のコンピューター（1000素数の場合）：

 Yours:
real    0m3.300s
user    0m3.284s
sys     0m0.000s

 Mine:
real    0m0.045s
user    0m0.040s
sys     0m0.004s
于 2013-03-18T00:06:03.513 に答える