```Issue #12665 has been reported by Jabari Zakiya.

----------------------------------------
Feature #12665: Faster prime? method for prime.rb std lib
https://bugs.ruby-lang.org/issues/12665

* Author: Jabari Zakiya
* Status: Open
* Priority: Normal
* Assignee:
----------------------------------------
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
```

--
https://bugs.ruby-lang.org/

Unsubscribe: <mailto:ruby-core-request / ruby-lang.org?subject=unsubscribe>
<http://lists.ruby-lang.org/cgi-bin/mailman/options/ruby-core>
```