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

Question

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?

Answer 1

Ruby has built in method to check if number is prime or not.

require 'prime'

Prime.prime?(2)  #=> true
Prime.prime?(4)  #=> false

Answer 2

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

First, we check for 0 and 1, as they're not prime. Then we basically just check every number less than num to see if it divides. However, as explained here, for every factor greater than the square root of num, there's one that's less, so we only look between 2 and the square root.

Update

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

Answer 3

The error you are getting is because you haven't required Primein your code, You need to do require Prime in your file.

One cool way I found here, to check whether a number is prime or not is following:

class Fixnum
  def prime?
    ('1' * self) !~ /^1?$|^(11+?)\1+$/
  end
end

10.prime?

Answer 4

From an algorithmic standpoint, checking if a number is prime can be done by checking all numbers up to and including (rounding down to previous integer) said number's square root.

For example, checking if 100 is prime involves checking everything up to 10. Checking 99 means only going to 9.

** Another way to think about it **
Each factor has a pair (3 is a factor of 36, and 3's pair is 12).
The pair is on the other side of the square root (square root of 6 is 36, 3 < 6, 12 > 6).
So by checking everything until the square root (and not going over) ensures you check all possible factors.

You can make it quicker by having a list of prime numbers to compare, as you are doing. If you have a maximum limit that's reasonably small, you could just have a list of primes and do a direct lookup to see if that number is prime.

Answer 5

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

lol sorry for resurrecting a super old questions, but it's the first one that came up in google.

Basically, it loops through possible divisors, using the square root as the max number to check to save time on very large numbers.

Answer 6

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

Answer 7

(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.

Answer 8

If you are going to use any Prime functions you must include the Prime library. This problem can be solved without the use of the prime library however.

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

Something like this would work.

Answer 9

Try this

def prime?(num)
    2.upto(Math.sqrt(num).ceil) do |i|
        break if num%i==0
        return true if i==Math.sqrt(num).ceil   
    end
    return false
end

Answer 10

So most of the answers here are doing the same thing in slightly different ways which is one of the cool things about Ruby, but I'm a pretty new student (which is why I was looking this up in the first place) and so here's my version with comment explanations in the code:

def isprime n # starting with 2 because testing for a prime means you don't want to test division by 1
  2.upto(Math.sqrt(n)) do |x| # testing up to the square root of the number because going past there is excessive
    if n % x == 0
      # n is the number being called from the program
      # x is the number we're dividing by, counting from 2 up to the square root of the number
      return false # this means the number is not prime
    else
      return true # this means the number is prime
    end 
  end
end