Rewrote #prime? to be much faster.

This new version executes an order of magnitude faster.

    require 'benchmark'
    require 'prime'

    def prime?(n)
      return true if n == 2
      return false if n % 2 == 0 || n < 2
      (3..(n**0.5).floor).step(2) { |i|
        return false if n % i == 0
      }
      true
    end

    # Current Method
    puts Benchmark.measure {
      (1..1_000_000).each { |i| i.prime? }
    }

    # Improved
    puts Benchmark.measure {
      # Current Method
      (1..1_000_000).each { |i| prime?(i) }
    }

    # Current Method
    puts Benchmark.measure {
      1000.times {
        (1..1_000).each { |i| i.prime? }
      }
    }

    # Improved
    puts Benchmark.measure {
      1000.times {
        (1..1_000).each { |i| prime?(i) }
      }
    }




I also didn't see a statistically significant difference between using % or
even?. However I also changed the order of the boolean checks which should
marginally improve performance.

old:
return false if value < 2 || value % 2 == 0

new:
return false if value.even? || value < 2

On Fri, Oct 10, 2014 at 2:36 PM, Marc-André Lafortune <
notifications@github.com> wrote:

> In lib/prime.rb:
>
> > @@ -155,14 +155,13 @@ def each(ubound = nil, generator = EratosthenesGenerator.new, &block)
> >    # == Parameters
> >    #
> >    # +value+:: an arbitrary integer to be checked.
> > -  # +generator+:: optional. A pseudo-prime generator.
> > -  def prime?(value, generator = Prime::Generator23.new)
> > -    return false if value < 2
> > -    for num in generator
> > -      q,r = value.divmod num
> > -      return true if q < num
> > -      return false if r == 0
> > -    end
> > +  def prime?(value)
> > +    return true if value == 2
> > +    return false if value < 2 || value % 2 == 0
>
> It might be more readable, but not really faster (for Fixnum). That's
> because % and == are optimized to not use method dispatch if possible.
>
> My gem doesn't find a statistically significant difference:
>
> require 'fruity'
> compare do
>   modulo { 42 % 2 == 0 }
>   even   { 42.even? }
> end
> # => even is similar to modulo
>
> —
> Reply to this email directly or view it on GitHub
> <https://github.com/ruby/ruby/pull/736/files#r18722644>.
>