public
Created

Partial patch for faster prime? and prime_division

  • Download Gist
gistfile1.diff
Diff
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70
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.

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.