Prime Numbers and Efficiency

Posted by fakebenjay on March 3, 2017

One of the more interesting code labs I’ve done here at Flatiron was the Prime numbers lab from the prework assignments. In the lab, the goal was to create a Ruby method that accepts an argument of a number, and returns true or false depending on whether or not it is prime.

By definition, a prime number is an integer that is divisible only by 1 and itself. Controlling for negative numbers, zero, and one, the most obvious logical path to determine such numbers involved taking the initial number, and dividing it by every number between 2 and the number itself. An early implementation of the code worked by returning false when the quotient of any number argument and divisor returned a remainder equalling zero, as follows.

def prime?(number)
  if number <= 1 || (number.to_f != number.to_i)
    return false
  elsif number == 2
    return true
  else
	array = (2..number).to_a
		array.each do |divisor|
		  for divisor in (2...number)
		    if (number.to_f % divisor.to_f) == 0
		      return false
		    end
		  end
		return true
	end
end

While the above method is very comprehensive, it’s also highly inefficient…

…and as an early implementation proved, that logic can also be highly error prone.

In that version, the method returned true for every odd multiple of 3, which obviously are not primes (thanks again to John Shelby for helping me pass those tests.)

So, once the code was working and had time to decompress from yelling at my computer, I realized that I was dividing by far too many numbers. Since the largest even divisor of any number is exactly half of that number, the array divisor could be changed as follows:

array = (2..number).to_a

array = (2..number/2).to_a

For smaller primes, the practical differences between working with either of those arrays is minimal. However, when debugging with larger numbers, minimizing the amount of divisors can be quite helpful. In that lab’s spec, it expected the #prime method to return false for 101,013 (which just so happens to be an odd multiple of three), scrolling through an array that goes up to 101,012 happens to take somewhat longer than an array that goes up to 50,506.

A few weeks later, I showed my mother (who works as a math teacher) my #prime method, and she mentioned that it’s possible to determine primes by dividing only up to their square roots. By changing the divisor array…

array = (2..Math.sqrt(number)).to_a

Math.sqrt(101013) = 317.825423779

…you can further reduce the number of divisors by literal orders of magnitude.


This got me thinking about a project a did in 7th grade about a 17th century French mathematician/friar named Marin Mersenne.

Mersenne devised a formula for finding prime numbers: 2^p − 1, where p is another prime number. Unfortunately, his formula didn’t work. It skipped many prime numbers (5 is not a Mersenne prime), and returned many non-primes (2^11 - 1 = 2047, which divides evenly into 23 and 89.)

Regardless, the formula is still used today to find prospective prime numbers as part of the Great Internet Mersenne Prime Search (GIMPS,) which takes theoretical prime numbers and uses the combined processing power of thousands of computers, all connected to the internet, to determine their prime statuses.

Keeping in mind that working with a six digit number was overly tedious with the earliest working version of the above method, working with the current highest known Mersenne prime, 2^74,207,281 - 1 (which clocks in at a reasonably-sized 22,338,618 digits), by dividing by every single number up to it would be insane. Likewise, dividing only up to the square root of that number would reduce the computational workload considerably.

It would seem to make sense that dividing up to square roots would be a good method for GIMPS to use when determining primes. However, they use a different method, the sieve of Eratosthenes. Erastothenes was an ancient Greek mathematician who determined primes by eliminating every multiple of a prime number from a range, starting with two, the lowest prime.

In the above graphic, Erastothenes’ sieve is able to pick out every prime number below 121 by the time it reaches 7. The next prime number, 11, is the square root of 121

The below method, #primes_till, found on Stack Exchange, returns every prime number in the range between 2 and n, where n is the argument, and seems to be, mathematically speaking, the best way to determine a prime number using Ruby. It does so by using Erastothenes’ sieve, and testing it only up to the square root of the argument n.

def primes_till(n)
  possible_primes = Array.new(n+1)

  (2..n).each do |n|
    possible_primes[n] = n
  end

  # numbers with multiples less than n
  (2..(Math.sqrt(n)).ceil).each do |i|
    if possible_primes[i]
      # remove all multiples of the prime
      (i**2..n).step(i).each do |x|
        possible_primes[x] = nil
      end
    end
  end
	possible_primes.compact
end