Sieve of Eratosthenes in PHP

The following code is an Implementation of the Sieve of Eratosthenes in PHP. It's purpose is to sieve the natural numbers and separate the primes from the composites.

    function find_primes($number)
    {
        global $primes;
        
        $nlist = array();
        $sqrt = ceil(sqrt($number));

        $nlist[] = 2;
        $nlist[] = 3;
        for($i=5 ; $i < $number ; $i=$i+2)
        {
            if($i%3 != 0)
                $nlist[] = $i;
        }
        
        for($i=2,$divisor=5; $divisor < $sqrt ; $i++) {
           /*
            * Remove non primes numbers from an array ($nlist)
            * Non prime numbers are identified by dividing with a known
            * prime (the prime number in our array at $index)
            */
            $count = count($nlist);
            $j = $i*$i;
            $nlist2 = array_slice($nlist,0,$j);
            
            for( ; $j

This code is a memory hog. If you try it with large numbers you might see an error such as the following. If you do the solution is to use the ini_set function to increase the momory limit. Eg: ini_set('memory_limit','256M');

PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 35 bytes) in /home/raditha/euler.php on line 19
← Back to home