From: TOYOFUKU Chikanobu <nobu_toyofuku@...>
Date: 2008-09-01T17:38:16+09:00
Subject: [ruby-dev:36072] Re: Refactoring of enumerating prime numbers

  豊福です。

In [ruby-dev :36067]
> 新しいprime.rbを添付します。

[ruby-dev:30937] Re: Integer#prime_division と Prime
に書いたささやかな最適化を取り込んでもらえたらと思います。
divmod と % の計算コストはほぼ同じですよね。

--- prime.rb.org
+++ prime.rb
@@ -87,8 +87,9 @@
   # +generator+:: optional. A pseudo-prime generator.
   def prime?(value, generator = Prime::Generator23.new)
     for num in generator
-      return true if value < num * num
-      return false if value % num == 0
+      q,r = divmod value num
+      return false if r == 0
+      return true if q <= num
     end
   end

@@ -135,7 +136,7 @@
       if count != 0
        pv.push [prime, count]
       end
-      break if prime * prime  >= value
+      break if value1 <= prime
     end
     if value > 1
       pv.push [value, 1]

---