That is a sieve.
I usually use sieves to sift my cake flour. Sifting cake flour means the bulky stuff is forced through these small holes. Thus, the flour ends up fine; finer and softer than sand.
Why must I sift my cake flour? So the finished cake is light as a feather and soft as silk and fluffy as a cotton fiber.
Math also needs sifting sometimes. Why have a bulky, indigestible rock when we can have something as fluffy as a chiffon cake?
2000 years ago, Eratosthenes thought so too. (Actually, chiffon cake was invented 1800 years later, but let’s not discuss that here.)
How many such primes are there between two given numbers $a$ and $b$?
You could solve this with brute force. Test all the numbers between or equal to $a$ and $b$.
But who wants too? If you had two large numbers, $1000000000$ and $2000000000$, the process would take years!
Eratosthenes knew that too.
He made his own sieve.
Explain what Eratosthenes’ sieve is.
If you think about it, any composite integer is equal to a prime multiplied by any other integer (prime or composite, it doesn’t matter, as long as it’s more than 1).
$1$ is definitely not prime. $2$ is prime, of course.
Let’s take all the multiples of $2$ within these boundaries… that are not $2$ itself, of course!
$4$, $6$, $8$ and so on, until $100$. Let’s cross them off.
The next number that isn’t crossed off is 3, so let’s cross off all of 3’s multiples.
The next number that hasn’t been crossed off is 5, so let’s cross off all of its multiples. And let’s keep going until we can’t cross any more.
We’re done with:
Have you notcied? This removes all of the composite numbers!
Now it’s easy to count how many primes there are.
How can I implement this in coding?
First, let’s try to solve this question:
How many primes are between $a$ and $b$, inclusive?
First, let’s try a simple case. $a = 1$ and $b = 10$.
Let’s create a vector array and call it
