pseudoramble
Goofing off With Prime Numbers Part 1 - The Sieve of Eratosthenes
Published on 2016-04-01 Modified on 2016-04-01

I am not fantastic at math. I've always found it interesting, but it's never come to me naturally. Sometimes it's good to face things you're not good at and give them a shot! So here we are, goofing off with prime numbers.

So first off, what is a prime number anyway?

Using a grade school explanation of it, prime numbers are natural numbers that can be evenly divided by two divisors - the number itself and 1.

A few things:

Okay, cool. So some number, itself, and 1. Got it.

What are some prime numbers?

A small sample would be {2, 3, 5, 7} .

How did you figure that out?

Let's first try out a real quick test for prime numbers between 1 and 10:

  1. ✘ Trick question. One isn't considered a prime number.
  2. ✔ That's our only option here!
  3. ✔ We can skip 3 / 3 and 3 / 2 = 1.5 doesn't work. So count 3!
  4. 4 / 2 = 2 so we can't count 4.
  5. 5 / 4 | 5 / 3 | 5 / 2 don't give us whole numbers. So count 5!
  6. 6 / 5 | 6 / 4 won't work. 6 / 3 = 2 so we can't count 6.
  7. 7 / 6 | 7 / 5 | 7 / 4 | 7 / 3 | 7 / 2 don't give us whole numbers. So count 7!
  8. 8 / 4 = 2 so we can't count 8.
  9. 9 / 3 = 3 so we can't count 9.
  10. 10 / 5 = 2 so we can't count 10.

Putting it together, you get the set {2, 3, 5, 7} .

You might notice a few things too:

You're finding all numbers that are multiples of something else . Once you've eliminated those numbers, you're left with the prime numbers! And that is the essence of the Sieve of Eratosthenes.

Here's a handy illistration from Wikipedia :

Sieve of Eratosthenes

So how do I find the prime numbers under 123,456?!

Running this by hand (or most algorithms really) can be tedious. Good thing we've got these shiny fancy computer boxes now. They're even internet-enabled now!

An implementation of this I put together in F# can be found here . The way I put together my implementation was probably not the most efficient, but I think is somewhat straight forward (here's a paired down form to show the idea):

let rec runTest multipliers limit removals =
    let multipler = List.head multipliers

    if multipler > int (sqrt (float limit))
    then
        removals
    else
        let updatedRemovals = generateStep multipler limit removals
        runTest (List.tail multipliers) limit updatedRemovals

let n = 123456
let startSeq = seq { for i in 2 .. n -> i }

runTest (List.ofSeq startSeq) n Set.empty
|> Set.diffeernce (Set.ofSeq startSeq)

A quick breakdown of the code above :

  1. First, check if we need to calculate more primes by looking at the next multiplier.
    1. If we do need to check, we generate the values from multiplier^2 to the upper bound specified.
    2. We that set of values with the previously calculated value to omit (see Set.union ).
    3. Repeat from #1.
  2. Once here, all the composite numbers have been found.
    1. These are removed from the range from 2 to the upper bound (see Set.difference ).
  3. You are now left with only prime numbers!

So there you have it - A way to find prime numbers. In Part 2, we'll goof around more by talking about how prime numbers actually can make any other natural number.