Partial patch for faster prime? and prime_division

gistfile1.diff

diff --git a/lib/ruby/1.9/prime.rb b/lib/ruby/1.9/prime.rb
index 4a20d93..9707fc2 100644
--- a/lib/ruby/1.9/prime.rb
+++ b/lib/ruby/1.9/prime.rb
@@ -25,13 +25,62 @@ class Integer
   # Returns the factorization of +self+.
   #
   # See Prime#prime_division for more details.
-  def prime_division(generator = Prime::Generator23.new)
-    Prime.prime_division(self, generator)
+  def prime_division(generator = nil)
+    return Prime.prime_division(self, generator) if (generator)
+    
+    seeds  = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
+    p = 13
+    
+    # find primes <= Pn, compute modPn then Prime Gen residues for Pn
+    primes = seeds[0..seeds.index(p)]; mod = primes.inject {|a,b| a*b }
+    residues=[1]; 3.step(mod,2) {|i| residues << i if mod.gcd(i) == 1}
+    residues << mod+1; rescnt = residues.size-1
+    
+    n = self.abs
+    factors = []
+    
+    return factors << n if primes.include? n
+    primes.each {|p| while n%p ==0; factors << p; n /= p end }
+    return factors if n == 1  # for when n is product of only seed primes
+    
+    sqrtN= Math.sqrt(n).to_i
+    modk,r=0,1; p=residues[1] # first test prime pj
+    while p <= sqrtN
+      if n%p == 0
+        factors << p; r -=1; n /= p; sqrtN = Math.sqrt(n).to_i
+      end
+      r +=1; if r > rescnt; r=1; modk +=mod end
+      p = modk+residues[r]    # next (or current) prime candidate
+    end
+    factors << n
+    factors.sort # return n if prime, or its prime factors
   end
 
   # Returns true if +self+ is a prime number, false for a composite.
   def prime?
-    Prime.prime?(self)
+    # from primzp with seed=13
+    seeds  = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]
+    p = 13
+    
+    n = self.abs
+    p = 5 if n < 510513   # use P5 prime generator for small numbers
+    
+    # find primes <= Pn, compute modPn then Prime Gen residues for Pn
+    primes = seeds[0..seeds.index(p)]; mod = primes.inject {|a,b| a*b }
+    residues=[1]; 3.step(mod,2) {|i| residues << i if mod.gcd(i) == 1}
+    residues << mod+1; rescnt = residues.size-1
+    
+    return true  if primes.include? n
+    return false if not residues.include?(n%mod) || n == 1
+    
+    sqrtN = Math.sqrt(n).to_i
+    modk,r=0,1; p=residues[1] # first test prime pj
+    while p <= sqrtN
+      return false if n%p == 0
+      r +=1; if r > rescnt; r=1; modk +=mod end
+      p = modk+residues[r]    # next prime candidate
+    end
+    return true
   end
 
   # Iterates the given block over all prime numbers.