# pseudoramble

## Goofing off With Prime Numbers Part 1 – The Sieve of Eratosthenes

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. ## 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 =

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. 2. If we do need to check, we generate the values from `multiplier^2` to the upper bound specified. 3. We that set of values with the previously calculated value to omit (see `Set.union`). 4. Repeat from #1.

2. Once here, all the composite numbers have been found. 6. 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.