## Feature #10354

### Optimize Integer#prime?

**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

**Related issues**

### Associated revisions

- lib/prime.rb: Remove useless loop and block capture. See [#10354]

- lib/prime.rb: Remove useless loop and block capture. See [#10354]

- lib/prime.rb: Remove useless loop and block capture. See [#10354]

- lib/prime.rb: Remove useless loop and block capture. See [#10354]

- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

- lib/prime.rb: Optimize Integer#prime? Patch by Nick Slocum [Bug #10354]

### History

#### #1 [ruby-core:65586] Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

Oups, it would help if I gave the right implementation for Bignum#prime? See below

Here are some benchmarks:

Benchmark over 1..1_000_000

Current prime lib: 15.54

Fixed prime lib: 7.13

Nick's: 2.49

Benchmark for ((1 << 65) + 5).prime?:

Current prime lib: 11.83

Fixed prime lib: 6.82

Nick's: 5.32

Mine: 4.91

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 = 3 (5..(self**0.5).floor).step(2) { |i| if (skip_division -= 1) == 0 skip_division = 3 next end return false if self % i == 0 } true end end

#### #2 [ruby-core:65633] Updated by nick_slocum (Nick Slocum) over 3 years ago

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

#### #3 [ruby-core:65975] Updated by marcandre (Marc-Andre Lafortune) over 3 years ago

Dear Yugui,

Do you have an objection that I commit my fixes (which are really bug fixes) while you decide if you want to go in the direction of Nick's optimization?

Thanks

#### #4 Updated by marcandre (Marc-Andre Lafortune) about 3 years ago

**Is duplicate of***Feature #5378: Prime.each is slow*added

#### #5 Updated by marcandre (Marc-Andre Lafortune) over 2 years ago

**Status**changed from*Open*to*Closed*