How can I test if a value is a prime number in Ruby? Both the easy and the hard way?

user_1542383 0
Viewed 31343

I am trying to create a program that will test whether a value is prime, but I don't know how. This is my code:

class DetermineIfPrime
def initialize (nth_value)
@nth_value = nth_value
primetest
end

def primetest
  if Prime.prime?(@nth_value)
   puts ("#{@nth_value} is prime")
  else
   puts ("This is not a prime number.")
  end
rescue Exception
puts ("#{$!.class}")
puts ("#{$!}")
 end
end

And every time I run that it returns this.

NameError
uninitialized constant DetermineIfPrime::Prime

I tried other ways to do the job, but I think this is the closest I can get.

I also tried this:

class DetermineIfPrime
def initialize (nth_value)
@nth_value = nth_value
primetest
end

 def primetest
 for test_value in [2, 3, 5, 7, 9, 11, 13] do
  if (@nth_value % test_value) == 0
   puts ("#{@nth_value} is not divisible by #{test_value}")
  else
   puts ("This is not a prime number since this is divisible by #{test_value}")
  break
  end
 end
 end
end

Or am I just doing something wrong?

ruby algorithm
10 Answers

In response to your question, while you can approach the problem by using Ruby's Prime I am going to write code to answer it on its own.

Consider that all you need to do is determine a factor that is smaller than the integer's square root. Any number larger than the integer's square root as a factor requires a second factor to render the number as the product. (e.g. square root of 15 is approx 3.8 so if you find 5 as a factor it is only a factor with the factor pair 3 and 5!!) 

    def isPrime?(num)
        (2..Math.sqrt(num)).each { |i| return false if num % i == 0}
        true
    end

Hope that helps!!

user_30114360

(To first answer the question: yes, you are doing something wrong. As BLUEPIXY mentions, you need to put require 'prime' somewhere above the line that calls Prime.prime?. Typically on line 1.)

Now, a lot of answers have been given that don't use Prime.prime?, and I thought it might be interesting to benchmark some of them, along with a possible improvement of my own that I had in mind.

###TL;DR

I benchmarked several solutions, including a couple of my own; using a while loop and skipping even numbers performs best.

Methods tested

Here are the methods I used from the answers:

require 'prime'

def prime1?(num)
  return if num <= 1
  (2..Math.sqrt(num)).none? { |i| (num % i).zero? }
end

def prime2?(num)
  return false if num <= 1
  Math.sqrt(num).to_i.downto(2) {|i| return false if num % i == 0}
  true
end

def prime3?(num)
  Prime.prime?(num)
end

def prime4?(num)
  ('1' * num) !~ /^1?$|^(11+?)\1+$/
end

prime1? is AndreiMotinga's updated version. prime2? is his original version (with the superfluous each method removed). prime3? is Reboot's, using prime library. prime4? is Saurabh's regex version (minus the Fixnum monkey-patch).

A couple more methods to test

The improvement I had in mind was to leverage the fact that even numbers can't be prime, and leave them out of the iteration loop. So, this method uses the #step method to iterate over only odd numbers, starting with 3:

def prime5?(num)
  return true if num == 2
  return false if num <= 1 || num.even?
  3.step(Math.sqrt(num).floor, 2) { |i| return false if (num % i).zero? }
  true
end

I thought as well that it might be interesting to see how a "primitive" implementation of the same algorithm, using a while loop, might perform. So, here's one:

def prime6?(num)
  return true if num == 2
  return false if num <= 1 || num.even?
  i = 3
  top = Math.sqrt(num).floor
  loop do
    return false if (num % i).zero?
    i += 2
    break if i > top
  end
  true
end

Benchmarks

I did a simple benchmark on each of these, timing a call to each method with the prime number 67,280,421,310,721. For example:

start = Time.now
prime1? 67280421310721
puts "prime1? #{Time.now - start}"

start = Time.now
prime2? 67280421310721
puts "prime2? #{Time.now - start}"

# etc.

As I suspected I would have to do, I canceled prime4? after about 60 seconds. Presumably, it takes quite a bit longer than 60 seconds to assign north of 6.7 trillion '1''s to memory, and then apply a regex filter to the result — assuming it's possible on a given machine to allocate the necessary memory in the first place. (On mine, it would seem that there isn't: I went into irb, put in '1' * 67280421310721, made and ate dinner, came back to the computer, and found Killed: 9 as the response. That looks like a SignalException raised when the process got killed.)

The other results are:

prime1? 3.085434
prime2? 1.149405
prime3? 1.236517
prime5? 0.748564
prime6? 0.377235

Some (tentative) conclusions

I suppose that isn't really surprising that the primitive solution with the while loop is fastest, since it's probably closer than the others to what's going on under the hood. It is a bit surprising that it's three times faster than Prime.prime?, though. (After looking at the source code in the doc it is less so. There are lots of bells and whistles in the Prime object.)

AndreiMotinga's updated version is nearly three times as slow as his original, which suggests that the #none? method isn't much of a performer, at least in this context.

Finally, the regex version might be cool, but it certainly doesn't appear to have much practical value, and using it in a monkey-patch of a core class looks like something to avoid entirely.

user_4904540
Related