The Sampson Project

Calculating Primes

« Back to Blogs

Learn how to efficiently calculate prime numbers for use in modular arithmetic


Prime numbers are a major part of many important functions in the Tech world, one of the most being their use in public-key cryptography. For instance, the ANSI X9.31 standard requires that RSA moduli not only be prime numbers, but more specifically they must be strong primes. In number theory, a strong prime is a prime number that is greater than the average of the nearest prime above and below it. To express a strong prime algebraically:

given a prime number P where i is the index of P in a list of prime numbers:

         (P₍ᵢ₋₁₎) + P₍ᵢ₊₁₎)

    Pᵢ > ––––––––––––––––––

                  2

As a literal example we can look at the number 11. The prime found just before 11 is 7, and the prime just after is 13. If we add 7 and 13 (20) and then divide by 2, we get 10. Because 11 > 10, 11 is the first strong prime in integer math.

Strong primes are calculated off of their location in the prime index, so to determine if a number is a strong prime, we need a way to create an array or hash of prime numbers. Once we have that, plugging our formula above should be a piece of cake

So now we know the types of primes and how to determine if they are strong, but how do we get a list of primes to compare in the first place? The answer to that question is what we will focus on today.

Training Wheels: The Brute Force Solution

The definition of a prime number is that it can only be cleanly divided by 1 and itself. So, to determine if a number is prime, we can modulo divide P by every number less than it. If modulo is never 0, than P is a prime number. In ruby, that might look something like this:

#set max prime
max = 100

#start at 2
n = 2

#create a blank primes array
primes = []

until n > max

  primes << n if (2...n).none? {|d| n % d == 0}
  n += 1

end

primes

# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

The problem with this method is even though it is space efficient (Space Complexity is O(n) where n is number of primes), it is extremely computationally inefficient. For every number between 0 and 100, you have to check every number below it. When we include a step tracker variable to see the total number of operations we end up with 1232 operations done in our until block. That makes the Time Complexity of this algorithm O(n²). We can do better.

Upgrade: The Sieve of Eratosthenes Solution

Sieve of Eratosthenes

In our earlier solution, every number has to be checked against every single, smaller number. But, what if we could cut out numbers we know will not be prime as we find new ones? That is the goal of the Sieve of Eratosthenes.

Using the Sieve of Eratosthenes, we start with every number between 2 and our max. Then each time we find a new prime, we remove all of its multiples from our list of numbers. Any remaining numbers are prime. In ruby, that might look something like this:

# set max
max = 100


# initialize primes array, include two nil values so that
# each index is the same as number at said index

primes = [nil, nil, *2..max]

# Because we are removing multiples, the highest number
# we have to run the seive on is the square root of your max
(2..Math.sqrt(max)).each do |p|

  # from i² to max, mark each multiple of i as nil if i is still
  # in the list of primes
  (i**2..max).step(i) { |m| primes[m] = nil }  if primes[i]

end

# compact primes array to remove nil values
primes = primes.compact

# => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Tracking the number of operations for this method, we end up with only 113 operations to find our primes. Since we eliminate unnecessary numbers, and quit as soon as mathematically possible we are able to bring the Time complexity of finding all primes less than a given a max down to O(n).

The drawback of a sieve, however, is that it is relatively space inefficient. In the brute force method we only store numbers after we find them; in a sieve of Eratosthenes, we have to originally store an index of every number between 0and max before we can compact it down when we are done with our computations. This gives us a Space Complexity of O(n) where n is the max number instead of the number of primes.

Wrapping Up: Space or Speed

Now that we have our array of primes, calculating strong primes is easy:

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

strong_primes = []

primes.each_with_index do |prime, i|
  if i > 0 && i < primes.length - 1
    strong_primes << prime if prime > (primes[i-1] + primes[i+1])/2
  end
end
strong_primes
# => [11, 17, 29, 37, 41, 59, 67, 71, 79]

In most algorithmic problems, there is a trade off between small, clean iterative solutions and their more complex computationally efficient counterparts. Which one you choose will depend on the situation, but what it almost always boils down to is the answer to the following question:

Do you need to use minimal space, or get maximum speed?