Skip to content

Instantly share code, notes, and snippets.

@headius headius/gist:5885551
Created Jun 28, 2013

Embed
What would you like to do?
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.