Prime numbers are pretty interesting, and there are lots of methods of finding primes, but today I want to talk about one of the oldest: the Sieve of Eratosthenes. (I think it's pronounced [ɛrətɒsθɛniz].)
This method is good for finding primes up to a given positive integer.
The first thing to do is create a list of numbers from 2 up to the number you're interested in, let's say 35: 2,3,4,5,...35.
The next step is to filter out all the numbers divisbile by 2, except 2.
2,3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35
Then find the first number that hasn't been filtered out. This number is also prime. That will be 3. Then filter the list for all numbers divisible by 3.
2,3,5,7,11,13,17,19,23,25,29,31,35
Keep doing this until you have no more numbers to filter and you will be left with a list of prime numbers.
2,3,5,7,11,13,17,19,23,29,31
So, now we can find prime numbers less than N. What if we wanted to find the Nth prime? We'll need a couple more steps.
The first question is, what is the limit we have to sieve to to find N primes? I'm no maths wiz, so I've been working off this rule of thumb.
If we look at the limit of 35, then we can see there are 11 primes. The limit of 100 has 25 primes, 1000 has 168 primes, 10000 has 1229 primes, 50000 has 5133 primes. However, the number of primes seems to get more sparse the greater the limits, for example 200000 has 17984 primes and 400000 has 33860 primes.
So, a good rule of thumb for me seems to be that your limit should be 20 times the N you're looking for, for an N that is computable in under a minute.
The other thing is that, for efficiency's sake, we can break out of the algorithm once we have N primes.
I've created a codepen to play around with it:
Top comments (1)
great article! really easy to understand