How to Test If a Value Is a Prime Number in Ruby? Both The Easy and The Hard Way

Ruby - determine if a number is a prime

It's because = is of higher precedence than or. See Ruby's operator precedence table below (highest to lowest precedence):

[ ] [ ]=
**
! ~ + -
* / %
+ -
>> <<
&
^ |
<= < > >=
<=> == === != =~ !~
&&
||
.. ...
? :
= %= { /= -= += |= &= >>= <<= *= &&= ||= **=
defined?
not
or and
if unless while until
begin/end

The problematic line is being parsed as...

(foundDivider = ((n % d) == 0)) or foundDivider

...which is certainly not what you mean. There are two possible solutions:

Force the precedence to be what you really mean...

foundDivider = (((n % d) == 0) or foundDivider)

...or use the || operator instead, which has higher precedence than =:

foundDivider = ((n % d) == 0) || foundDivider

Is there a simple algorithm that can determine if X is prime?

The first algorithm is quite good and used a lot on Project Euler. If you know the maximum number that you want you can also research Eratosthenes's sieve.

If you maintain the list of primes you can also refine the first algo to divide only with primes until the square root of the number.

With these two algoritms (dividing and the sieve) you should be able to solve the problems.

Edit: fixed name as noted in comments

How do I generate the first n prime numbers?

In Ruby 1.9 there is a Prime class you can use to generate prime numbers, or to test if a number is prime:

require 'prime'

Prime.take(10) #=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Prime.take_while {|p| p < 10 } #=> [2, 3, 5, 7]
Prime.prime?(19) #=> true

Prime implements the each method and includes the Enumerable module, so you can do all sorts of fun stuff like filtering, mapping, and so on.

List of prime numbers using Array methods

Ruby 1.9 has a very nice Prime class:

http://www.ruby-doc.org/core-1.9/classes/Prime.html

But I'm assuming you don't care about any standard classes, but want to see some code, so here we go:

>> n = 100 #=> 100
>> s = (2..n) #=> 2..100
>> s.select { |num| (2..Math.sqrt(num)).none? { |d| (num % d).zero? }} 
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Note: I wrote it this way because you wanted Enumerable methods, for efficiency's sake you probably want to read up on prime finding methods.

How do I efficiently sieve through a selected range for prime numbers?

I haven't looked fully, but one factor is that, you are replacing a certain value in primes with nil, and later compact-ing it to remove them. This is a waste. Just by doing that directly with delete_at makes it more than twice fast:

def ranged_sieve2(l, b)
  primes = (l..b).to_a
  primes.delete_at(0) if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes.delete_at(index) if index
    end
  end
  primes
end

ranged_sieve(1, 100) # => Took approx 8e-4 seconds on my computer
ranged_sieve2(1, 100) # => Took approx 3e-4 seconds on my computer

Another point to improve is that, using a hash is much faster than array as the relevant size gets larger. Replacing your array implementation with a hash, you can get this:

def ranged_sieve3(l, b)
  primes = (l..b).inject({}){|h, i| h[i] = true; h}
  primes.delete(0)
  primes.delete(1)
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      primes.delete(stepped)
    end
  end
  primes.keys
end

When you do range_sieve3(1, 100) with this, it is slower than range_sieve2(1, 100) because of the overhead. But as you make the number larger, the superiority becomes salient. For example, I got this result on my computer:

ranged_sieve(1, 1000) # => Took 1e-01 secs
ranged_sieve2(1, 1000) # => Took 3e-02 secs
ranged_sieve3(1, 1000) # => Took 8e-04 secs

Check if two arrays have the same contents (in any order)

This doesn't require conversion to set:

a.sort == b.sort

---

Related Topics