Sieve of Eratosthenes in PHP

As mentioned in my last article, I started doing some challenges from the Programming Praxis website. And here comes my PHP solution to the second challenge.

My first approach was to generate an array containing all the elements and removing them one by one, as in the exact paper version of the algorithm. Aside the fact that I had to allocate PHP 1GB+ memory in order for him to generate the array, it took ages to complete.

This made me took a different approach. First make a list for all the elements that I was going to use for finding prime numbers; from 2 to sqrt(n) and afterward go over all the numbers up to the limit and test them against all the numbers. If the number is not dividable with any other number from the list, then add it to the prime list.

Flattr this
blog comments powered by Disqus