* lib/mathn.rb (Integer): moved into prime.rb.

  (Prime): ditto.

* lib/prime.rb (Integer): moved from mathn.rb.
  (Integer.each_prime): added.
  (Integer#prime?): added.
  (Prime): moved from mathn.rb.
    Its implmentation was rewritten. see [ruby-dev:35863].
    And patched by Keiju ISHITSUKA <keiju@ishitsuka.com>,
    see [ruby-dev:36128].
  (Prime.new):                     obsolete.
  (Prime.instance):                added.
  (Prime.each):                    added.
  (Prime.int_from_prime_division): added.
  (Prime.prime_division):          added.
  (Prime.prime?):                  added.
    Patch by TOYOFUKU Chikanobu
    <nobu_toyofuku at nifty.com> in [ruby-dev:36067].
  (Prime.cache):                   removed.
  (Prime.primes):                  removed.
  (Prime.primes_so_far):           removed.
  (Prime#int_from_prime_division): added.
  (Prime#prime_division):          added.
  (Prime#prime?):                  added.
  (Prime#primes):                  removed.
  (Prime#primes_so_far):           removed.
  (Prime::PseudoPrmeGenerator):    added.
  (Prime::EratosthenesGenerator):  added.
  (Prime::TrialDivisionGenerator): added.
  (Prime::Generator23):            added.
  (Prime::TrialDivision):          added.
    Extracted from the previous implementation of Prime
    by Keiju ISHITSUKA.
  (Prime::EratosthenesSieve):      added.

* lib/.document (prime.rb): added

* lib/README (prime.rb): added

* test/test_prime.rb: added.

git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19095 b2dd03c8-39d4-4d8f-98ff-823fe69b080e

1 files changed, 1 insertions, 95 deletions

diff --git a/lib/mathn.rb b/lib/mathn.rb
index ce1acc927f..2af2b83da3 100644
--- a/lib/mathn.rb
+++ b/lib/mathn.rb
@@ -12,101 +12,7 @@
 require "complex.rb"
 require "rational.rb"
 require "matrix.rb"
-
-class Integer
-
-  def Integer.from_prime_division(pd)
-    value = 1
-    for prime, index in pd
-      value *= prime**index
-    end
-    value
-  end
-  
-  def prime_division
-    raise ZeroDivisionError if self == 0
-    ps = Prime.new
-    value = self
-    pv = []
-    for prime in ps
-      count = 0
-      while (value1, mod = value.divmod(prime)
-	     mod) == 0
-	value = value1
-	count += 1
-      end
-      if count != 0
-	pv.push [prime, count]
-      end
-      break if prime * prime  >= value
-    end
-    if value > 1
-      pv.push [value, 1]
-    end
-    return pv
-  end
-end
-  
-class Prime
-  include Enumerable
-  # These are included as class variables to cache them for later uses.  If memory
-  #   usage is a problem, they can be put in Prime#initialize as instance variables.
-
-  # There must be no primes between @@primes[-1] and @@next_to_check.
-  @@primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
-  # @@next_to_check % 6 must be 1.  
-  @@next_to_check = 103            # @@primes[-1] - @@primes[-1] % 6 + 7
-  @@ulticheck_index = 3            # @@primes.index(@@primes.reverse.find {|n|
-                                   #   n < Math.sqrt(@@next_to_check) })
-  @@ulticheck_next_squared = 121   # @@primes[@@ulticheck_index + 1] ** 2
-
-  class << self
-    # Return the prime cache.
-    def cache
-      return @@primes
-    end
-    alias primes cache
-    alias primes_so_far cache
-  end
-  
-  def initialize
-    @index = -1
-  end
-  
-  # Return primes given by this instance so far.
-  def primes
-    return @@primes[0, @index + 1]
-  end
-  alias primes_so_far primes
-  
-  def succ
-    @index += 1
-    while @index >= @@primes.length
-      # Only check for prime factors up to the square root of the potential primes,
-      #   but without the performance hit of an actual square root calculation.
-      if @@next_to_check + 4 > @@ulticheck_next_squared
-        @@ulticheck_index += 1
-        @@ulticheck_next_squared = @@primes.at(@@ulticheck_index + 1) ** 2
-      end
-      # Only check numbers congruent to one and five, modulo six. All others
-      #   are divisible by two or three.  This also allows us to skip checking against
-      #   two and three.
-      @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
-      @@next_to_check += 4
-      @@primes.push @@next_to_check if @@primes[2..@@ulticheck_index].find {|prime| @@next_to_check % prime == 0 }.nil?
-      @@next_to_check += 2 
-    end
-    return @@primes[@index]
-  end
-  alias next succ
-
-  def each
-    return to_enum(:each) unless block_given?
-    loop do
-      yield succ
-    end
-  end
-end
+require "prime.rb"
 
 class Fixnum
   remove_method :/