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:

• By natural number, I mean whole number (no decimals or complex numbers or crazy things) > 0.
• By divisors, I mean a denominator. So in 10 / 2 = 5 , it would be 2.
• Those factors are the number itself ( n lets say) and the number 1.

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:

• All of the even numbers are omitted (save for 2). So right away you knocked out 4, 6, 8, and 10.
• All of the numbers that are multiples of 3 were removed (save for 3). So you could eliminate 6 and 9.
• Even if we somehow missed that 10 / 2 = 5, we would catch that 10 / 5 = 2.
  • In other words, multiples of 5 disappear.

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 :

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.