Ruby program for prime number (Prime class + Sieve of Eratosthenes)

Table of Contents

1. Introduction
2. What is a prime number
3. Using Ruby's Prime class
4. What is Sieve of Eratosthenes
5. Define your own method
6. Conclusion

Introduction

In the article at OpenGenus, we will be talking about the methods used to find prime numbers using the Ruby coding language. Methods such as the Ruby Prime class, Sieve of Eratosthenes and many others will be covered.

What is a prime number

To first find a prime number we must know what we are looking for, So what is a prime number? A prime number is simply a whole number that is divisible by 1 and the number itself with out a remainder (e.g. 2,3,5,7,11) all of these numbers can only be divided by 1 and the number itself and leave you with a remainder of zero. A prime number can only have two factors 1 and the number itself.

Using Ruby's Prime class

Ruby's prime class is a representation of a set of all prime numbers. To use the prime class , you must first 'require' it in your code.

require "prime"

This class is also Enumerable so they are a series of methods you can use within this class to retrieve prime numbers as needed.
Example 1.

Prime.first(5) #=>[2, 3, 5, 7, 11]

Example 2.

prime = Prime.take_while {|p| p < 10}
print prime #=> [2, 3, 5, 7]

Example 3

Prime.each(20) do |prime|
    puts prime #=> [2, 3, 5, 7, 11, 17, 19]
end

In the Example 1 we use the "first" method to get the first 5 prime numbers of the numbering sequence. For Example 2 we use the "take_while" method to take all the prime numbes less than 10. Example 3 is pretty much the same but we use "each" method instead, this allows us to find all the prime numbers within the range of 1 and 20.

What is Sieve of Eratosthenes

Sieve of Eratosthenes is an algorithm used for finding all prime numbers up to any given limit. This is achieved by making a list of all integers form 2 through N (N being the last number) we then mark 2 as a prime number and proceed to eliminated all the multiples of 2 till we reach N. This process is repeated for 3 which is the next uneliminated number and therefore becomes the next prime number, this time we eliminate all the multiples of 3, we would skip 4 because it was already eliminated being a multiple of 2 so the next prime number would be 5 and we would eliminate all the multiples of 5. You begin to see the pattern with the sieve of eratosthenes method, this pattern would continue until you reach an uneliminated number when squared it's total is bigger than N (11 x 11 = 121 but N is 120) at this point any uneliminated number between 11 and 120 would be considered a prime number

def sieve_of_eratosthenes(n)
  # Create a boolean array "prime[0..n]" and initialize
  # all entries as true. A value in prime[i] will
  # finally be false if i is Not a prime, else true.
  prime = Array.new(n + 1, true)
  
  # Start with the smallest prime number, which is 2.
  p = 2
  while p * p <= n do
    # If prime[p] is not changed, then it is a prime.
    if prime[p] == true
      # Update all multiples of p.
      (p * p).step(n, p) do |i|
        prime[i] = false
      end
    end
    p += 1
  end
  
  # Print all prime numbers.
  primes = []
  (2..n).each do |i|
    primes << i if prime[i]
  end
  primes
end

# Example usage:
p sieve_of_eratosthenes(20) #=> [2, 3, 5, 7, 11, 13, 17, 19]

We can also use the EratosthenesGenerator object along with the prime class to tell you if a number is a prime number

require 'prime'

num = 97
primes = Prime::EratosthenesGenerator.new.take_while {|i| i <= num}

primes.include?(num)  #=> true

Define your own method

If the method above seem too easy or still confusing you can make your own methods. One such way is using the each loop

def is_prime?(n)
  # Check if n is divisible by any integer from 2 to sqrt(n).
  (2..Math.sqrt(n)).each do |i|
    return false if n % i == 0
  end
  return true
end

def find_primes(n)
  # Find all prime numbers less than or equal to n.
  primes = []
  (2..n).each do |i|
    primes << i if is_prime?(i)
  end
  primes
end

# Example usage:
p find_primes(20) #=> [2, 3, 5, 7, 11, 13, 17, 19]

As you can see we have 2 methods, the first one uses each to let us know if 'n' is a prime number and the second method returns an array of all the prime numbers between 2 and 'n'. So we call the first method inside the second method and if this condition is true primes << i if is_prime?(i) we push the number to the primes array.

Conclusion

Finding prime numbers within any range of numbers is made easy with ruby , weather you are using the Prime class the sieve of eratosthenes algorithm or you just use a simple each loop, All of them work and they do the same thing it's just a matter of preference, so which one will you choose?