Skip to content

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
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
Something went wrong with that request. Please try again.