From: nslocum@...
Date: 2014-10-12T20:44:13+00:00
Subject: [ruby-core:65633] [ruby-trunk - Feature #10354] Optimize	Integer#prime?

Issue #10354 has been updated by Nick Slocum.


I rewrote #prime? again using a better algorithm. It's about 2x faster.  This version is for `Integer`, but could be reworked for `BigNum`.

~~~
class Integer
  def prime?
    return self >= 2 if self <= 3
    return false if self % 2 == 0 or self % 3 == 0
    (5..(self**0.5).floor).step(6).each do |i|
      if self % i == 0 || self % (i + 2) == 0
        return false
      end
    end
    true
  end
end
~~~

Benchmarked with ruby-2.1.3
  my first version: 4.27
  this latest version: 2.76

----------------------------------------
Feature #10354: Optimize Integer#prime?
https://bugs.ruby-lang.org/issues/10354#change-49365

* Author: Marc-Andre Lafortune
* Status: Open
* Priority: Normal
* Assignee: Yuki Sonoda
* Category: lib
* Target version: current: 2.2.0
----------------------------------------
Nick Slocum shows in https://github.com/ruby/ruby/pull/736 that Integer#prime? can be optimized quite a bit.

First, that's because there are some basic things to avoid in the current lib, like needlessly capturing blocks and there's a useless `loop do` too.

I'm attaching a patch that fixes many of these things.

Even after these fixes applied, Nick's version is still faster and I don't see why we would not use it for Fixnum#prime?

For Bignum#prime?, since division costs more, we can go slightly faster with the following implementation:

    class Integer
      # Returns true if +self+ is a prime number, else returns false.
      def prime?
        return true if self == 2
        return false if self % 2 == 0 || self % 3 == 0 || self < 2
        skip_division = true
        (5..(self**0.5).floor).step(2) do |i|
          return false if skip_division && self % i == 0
          skip_division = !skip_division
        end
        true
      end
    end


---Files--------------------------------
prime_opt.patch (1.55 KB)


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