Instantly share code, notes, and snippets.

# headius/gist:5885551 Created Jun 28, 2013

Partial patch for faster prime? and prime_division
 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.