Project

General

Profile

Actions

Feature #10354

closed

Optimize Integer#prime?

Added by marcandre (Marc-Andre Lafortune) over 9 years ago. Updated over 8 years ago.

Status:
Closed
Target version:
-
[ruby-core:65580]

Description

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) prime_opt.patch marcandre (Marc-Andre Lafortune), 10/10/2014 03:22 AM

Related issues 1 (0 open1 closed)

Is duplicate of Ruby master - Feature #5378: Prime.each is slowClosedyugui (Yuki Sonoda)Actions
Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0