Optimizing prime-number detection by short-circuiting when a zero remainder is found

prime_detector.rb

require 'benchmark'
require 'prime'

class Integer
  def simple_prime?
    (2..Math.sqrt(self).floor).all? { |i| (self % i).nonzero? }
  end

  def clever_prime?
    return true  if self == 2
    return false if self.even?
    3.step(Math.sqrt(self).floor, 2).all? { |i| (self % i).nonzero? }
  end

  def short_circuit_prime?
    return true  if self == 2
    return false if self.even?
    !3.step((self ** 0.5).floor, 2).find { |i| (self % i).zero? }
  end
end

range = 2..1_000_000

Benchmark.bmbm do |bench|
  bench.report('simple:') { range.each &:simple_prime? }
  bench.report('clever:') { range.each &:clever_prime? }
  bench.report('short circuit:') { range.each &:short_circuit_prime? }
  bench.report('stdlib:') { range.each &:prime?        }
end

Related: http://talks.chastell.net/src-2011/#131 :)

That is interesting. I didn't think about #all? short circuiting when it hits a falsy value. I was thinking of it along the lines of Array#select vs Array#detect.

I did find a pretty slight improvement going from #any? to #find, though. It was just a few percent, probably due to not having to convert truthy/falsy values into actual true and false.

Also, another thing that surprised me was that switching from Math.sqrt(self) to self ** 0.5 gave a pretty big boost. Switching your code above to use it knocked about a second off on my machine under Rubinius (far less pronounced on MRI 2.0, though).