How to check if a value is a prime in Ruby? And the easy and hard way?

Question

I am trying to create a program that will check if a value is simple, but I do not know how to do it. 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 it, it returns it.

 NameError uninitialized constant DetermineIfPrime::Prime 

I tried other ways to do this work, 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 a built-in method to check if a 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 0 and 1, as they are not primary. Then we basically just check each number less than num to see if it divides. However, as explained here , for each factor greater than the square root of num , there is less, so we look only 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 get is that you do not need Prime in your code, you need to make require Prime in your file.

Here I found one cool way to check if a number is prime or not:

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

Answer 4

From an algorithmic point of view, checking whether a number is prime can be done by checking all the numbers before and including (rounding to the previous integer) the square root number.

For example, checking that 100 is primary involves checking only up to 10. Checking 99 means only 9.

** Another way to think about it **
Each factor has a pair (3 - coefficient 36, and 3 pairs - 12).
The pair is on the other side of the square root (the square root of 6 is 36, 3 <6, 12> 6).
Therefore, checking everything until the square root (and does not go over), you check all the possible factors.

You can do it faster by having a list of primes to compare how you do it. If you have a maximum limit that is small enough, you can simply have a list of primes and do a direct search 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 super old questions, but this is the first that appeared on google.

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

Answer 6

In answer to your question, although you can approach the problem using Ruby Prime, I am going to write code to answer it myself.

Keep in mind that all you have to do is determine a coefficient that is less than the integer square root. Any number greater than the integer square root as a factor requires a second factor to display the number as a product. (for example, the square root of 15 is about 3.8, so if you find 5 as a factor, then this is just a factor with a couple of factors 3 and 5!)

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

Hope this helps!

Answer 7

If you intend to use any of the basic functions, you must include the Prime library. However, this problem can be solved without using the main library.

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

Something like this will work.

Answer 8

try it

 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 9

So, most of the answers here do the same things in slightly different ways, which is one of the most interesting things in Ruby, but I'm a fairly new student (which is why I watched this in the first place) and therefore here is my version with comment comments 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 

Answer 10

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

Now many answers have been given that do not use Prime.prime? , and I thought it would be interesting to compare some of them, along with my own possible improvement, which I had in mind.

TL DR

I tested several solutions, including a couple of my own; it’s best to use a while and skip even numbers.

Methods Verified

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? - An updated version of AndreiMotinga. prime2? - its original version (without the extra method each ). prime3? is a reboot using the prime library. prime4? - Saurabh regex version (except Fixnum monkey patch).

A couple more methods to check

The improvement I had in mind was to take advantage of the fact that even numbers cannot be prime and to exclude them from the iteration loop. Thus, this method uses the #step method to iterate over only odd numbers, starting at 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 also thought it would be interesting to see how a “primitive” implementation of the same algorithm could be performed using a while . So here is 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 test for each of them, calculating the call time of each method with a prime number of 67,280,421,310,721. For instance:

 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 this, I canceled prime4? after about 60 seconds. Presumably, it takes more than 60 seconds to assign a memory of 6.7 trillion '1' to the north, and then apply a regular expression filter to the result, assuming that you can allocate the required amount of memory on this computer. (In my opinion, this is not so: I went into irb , inserted '1' * 67280421310721 , cooked and ate lunch, went back to the computer and found Killed: 9 as an answer. It looks like SignalException raised when the process was killed.)

Other results:

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

Some (preliminary) conclusions

I believe that it is not surprising that a primitive solution with a while loop is the fastest, since it is probably closer than others to what happens under the hood. Although it’s a little surprising that it is three times faster than Prime.prime? . (After looking at the source code in the document, it became less noticeable. There are a lot of bells and whistles in the Prime object.)

The updated version of AndreiMotinga is almost three times slower than its original, which suggests that the #none? method #none? not very effective, at least in this context.

Finally, the regex version may be cool, but it doesn't seem to have much practical value, and using it in a base class monkey patch looks like something that should be completely avoided.