Feature #12665
closed
Faster prime? method for prime.rb std lib
Description
The current version of the method prime? in the prime.rb
std lib replaced the older version starting with 2.3.0.
It uses an implementation of the P3 Strictly Prime, Prime Generator (SP PG).
It can be simplified as shown below.
(see Primes-Utils Handbook for details )
(https://www.scribd.com/doc/266461408/Primes-Utils-Handbook )
A much faster version primep5? can replace it using the P5 SP PG.
This allows it to be used with bigger numbers with much better performance.
class Integer
def prime? # version now used in prime.rb since MRI 2.3.0
return self >= 2 if self <= 3
return false if self % 2 == 0 or self % 3 == 0
# return false unless 6.gcd(self) == 1 # simplification
(5..(self**0.5).floor).step(6).each do |i|
if self % i == 0 || self % (i + 2) == 0
return false
end
end
true
end
def primep5? # Uses P5 Strictly Prime PG
return false unless self > 1 and 30.gcd(self) == 1 or [2,3,5].include? self
(7..Math.sqrt(self).to_i).step(30) do |p|
return false if
self%(p) == 0 or self%(p+4) == 0 or self%(p+6) == 0 or self%(p+10) == 0 or
self%(p+12) == 0 or self%(p+16) == 0 or self%(p+22) == 0 or self%(p+24) == 0
end
true
end
end
``
Beloow are some timing comparisions for 3 progressively larger primes for 2.3.1.
System: System76 3.5GHz I7 cpu laptop, Linux 64-bit OS
n1 = 100_000_000_000_000_003
n2 = 200_000_000_000_000_003
n3 = 1_000_000_000_000_000_003
n1 n2 n3
prime? 4.1 5.7 12.9
primep5 2.5 3.6 7.9
def tm; s = Time.now; yield; Time.now - s end
irb(main):028:0> n = 100_000_000_000_000_003; tm{ n.prime? }
=> 4.127392644
irb(main):029:0> n = 100_000_000_000_000_003; tm{ n.primep5? }
=> 2.539485672
irb(main):030:0> n = 200_000_000_000_000_003; tm{ n.prime? }
=> 5.721895509
irb(main):031:0> n = 200_000_000_000_000_003; tm{ n.primep5? }
=> 3.56925564
irb(main):032:0> n = 1_000_000_000_000_000_003; tm{ n.prime? }
=> 12.940908142
irb(main):033:0> n = 1_000_000_000_000_000_003; tm{ n.primep5? }
=> 7.920408959
Updated by 
Updated by