Finding Prime Numbers in Ruby and Python, and which is faster

I write stuff on my site sometimes, and a friend told me to try it this way...so here we go. This is lifted from a blog post I wrote earlier. Hopefully I don't screw anything up when I paste it over.

A month or two ago (I think? Between kids and Turing, I have no sense of time), one of our technical practice problems was figuring out how to implement the Sieve of Eratosthenes. I got a little obsessed over that weekend trying to figure out a more efficient way to do it than I had initially. With this, I ended up just trying to find prime numbers, but the Sieve of Eratosthenes is interesting.

For whatever reason, I was discussing this with a teacher after graduation, and she told me I should try it in Python to see the speed difference between Ruby and Python...and here we are. I'll talk it through in Ruby because that is how I did it initially, but I also do it in Python to get a comparison of how quickly it runs.

First, I needed to require the benchmark module to test the speed later. If you want to learn about benchmark, this link is informative. I named the method and set it to pass one parameter, the max number, so it knows what range to look for prime numbers in.

I created the array numbers to the size of max + 1 (because arrays are zero-indexed, and I don't want to lose the max number). Each index is set to the initial value of true to indicate whether or not it is prime. Everything will start out as true, but if it is found to not be a prime number, it will switch to false. Initially, I had been removing numbers from the array if they were not prime, but I have since learned (and correct me if I'm wrong) that pulling something out of an array is way less efficient because it requires everything to shift over, instead of just changing something inside the array.

require 'benchmark' #to test how quick it runs later

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
end        

Next, I need to set the first two indices, 0 and 1, to false because 0 and 1 are not prime numbers.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
end        

Now it is time to do a little math. This line will start a loop that iterates over the numbers from 2 to whatever the square root of max is. That is the upper limit because if a number has a factor larger than the square root, it will have a corresponding factor smaller than the square root. On a side note, here is an example explaining that.

The square root of 36 is 6

The factors of 36 are 
  1, 2, 3, 6, 9, 12, 18, 36

Every factor above the square root, 6, has a corresponding factor that is less than 6
9 * 4 = 36
12 * 3 = 36
18 * 2 = 36
36 * 1 = 36
Each pair has one number larger, and one number smaller than 6        

Anyway, back to the code. This following line uses the range from 2 to the square root of whatever the max is, and each of those numbers gets iterated over to check if it has a smaller factor than the square root. I'll use the variable pp (because it is shorter than possible_prime) to hold the number being checked

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
end        

We need to take pp and use that to check the numbers array for whether or not it is prime. If it is still marked as true (which means it is still considered prime), then it will go through and mark the multiples as not prime. It takes pp and multiplies it by each number in the range pp..max, and uses step to go through each one in that range. Each of those that you get is iterated over separately as multiple, and multiple is used to turn any of those false.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
    if numbers[pp]
      (pp*pp..max).step(pp) { |multiple| numbers[multiple] = false }
    end
  end
end        

Awesome, and now that all of those are found, then it iterates over the numbers array and will pull out the index of each one that is true because true tells you it's prime.

require 'benchmark'

def find_prime_numbers(max)
  numbers = Array.new(max + 1, true)
  numbers[0] = numbers[1] = false
  (2..Math.sqrt(max)).each do |pp|
    if numbers[pp]
      (pp*pp..max).step(pp) { |multiple| numbers[multiple] = false }
    end
  end
  numbers.each_index.select { |pp| numbers[pp] }
end        

And that should find all prime numbers between 0 and whatever you set the max as.

Time to set up benchmark

I will give it the variable name time and then run benchmark in there. It should run it, and return "Found (however many) prime numbers up to (whatever the max is)"

time = Benchmark.measure do
  primes = find_prime_numbers(max_val)
  puts "Found #{primes.size} prime numbers up to #{max_val}."
end        

I will set max_val at 1,000,000 and see what that gets me. If you want to learn how to read benchmark times, go here.

It took .157 seconds to run the above code, with the max value being 1,000,000

It took 1.705 seconds to run it when the max value was 10,000,000

It took 18.728 seconds when the max value was 100,000,000

I'm just going to put the python code below, it is about as similar as I could get it, and then run the same two numbers to compare.

import math
import time

def find_prime_numbers(max):
    numbers = [True] * (max + 1)
    numbers[0] = numbers[1] = False
    for pp in range(2, int(math.sqrt(max)) + 1):
        if numbers[pp]:
            for multiple in range(pp * pp, max + 1, pp):
                numbers[multiple] = False
    return [pp for pp, is_prime in enumerate(numbers) if is_prime]

def benchmark_prime(max_val):
    start_time = time.time()
    numbers = find_prime_numbers(max_val)
    end_time = time.time()
    print(f"Found {len(numbers)} prime numbers up to {max_val} in {end_time - start_time} seconds.")

if __name__ == "__main__":
    max_val = 1000000  
    benchmark_prime(max_val)        

When I ran that with 1,000,000, it finished in .091 seconds

It got 10,000,000 in 1.638 seconds

It got 100,000,000 in 21.066 seconds

In conclusion, my unscientific tests show that Python got it a little faster until I tried 100,000,000. I ran it several times, and there was some variation, but it seemed to live around that time.

Anyway, this was an interesting comparison between the two languages and something fun to play around with. As always, let me know if you know of a better way to do/explain any of this!