Project Euler || Question 10

I'm attempting to solve Project Euler in PHP and running into a problem with my for loop conditions inside the while开发者_高级运维 loop. Could someone point me towards the right direction? Am I on the right track here?

The problem, btw, is to find the sums of all prime numbers below 2,000,000

Other note: The problem I'm encountering is that it seems to be a memory hog and besides implementing the sieve, I'm not sure how else to approach this. So, I'm wondering if I did something wrong in the implementation.

<?php

// The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
// Additional information:
//   Sum below 100: 1060 
//        1000: 76127
//  (for testing)

// Find the sum of all the primes below 2,000,000.

// First, let's set n = 2 mill or the number we wish to find
// the primes under.

$n = 2000000;

// Then, let's set p = 2, the first prime number.

$p = 2;

// Now, let's create a list of all numbers from p to n.

$list = range($p, $n);

// Now the loop for Sieve of Eratosthenes.
// Also, let $i = 0 for a counter.

$i = 0;

while($p*$p < $n)
{
// Strike off all multiples of p less than or equal to n

  for($k=0; $k < $n; $k++)
  { 
      if($list[$k] % $p == 0)
      {
         unset($list[$k]);
      }
  }

 // Re-initialize array

 sort ($list);

 // Find first number on list after p. Let that equal p.

 $i = $i + 1;

 $p = $list[$i];

 }

 echo array_sum($list);

?>

---

You can make a major optimization to your middle loop.

  for($k=0; $k < $n; $k++)
  { 
      if($list[$k] % $p == 0)
      {
         unset($list[$k]);
      }
  }

By beginning with 2*p and incrementing by $p instead of by 1. This eliminates the need for divisibility check as well as reducing the total iterations.

 for($k=2*$p; $k < $n; $k += $p)
 { 
       if (isset($list[k])) unset($list[$k]);  //thanks matchu!
 }

The suggestion above to check only odds to begin with (other than 2) is a good idea as well, although since the inner loop never gets off the ground for those cases I don't think its that critical. I also can't help but thinking the unsets are inefficient, tho I'm not 100% sure about that.

Here's my solution, using a 'boolean' array for the primes rather than actually removing the elements. I like using map,filters,reduce and stuff, but i figured id stick close to what you've done and this might be more efficient (although longer) anyway.

    $top = 20000000;
    $plist = array_fill(2,$top,1);
    for ($a = 2 ; $a <= sqrt($top)+1; $a++) 
    {
        if ($plist[$a] == 1)
            for ($b = ($a+$a) ; $b <= $top; $b+=$a)
            {
                $plist[$b] = 0;
            }
    }

    $sum = 0;
    foreach ($plist as $k=>$v)
    {
        $sum += $k*$v;
    }
    echo $sum;  

When I did this for project euler i used python, as I did for most. but someone who used PHP along the same lines as the one I did claimed it ran it 7 seconds (page 2's SekaiAi, for those who can look). I don't really care for his form (putting the body of a for loop into its increment clause!), or the use of globals and the function he has, but the main points are all there. My convenient means of testing PHP runs thru a server on a VMWareFusion local machine so its well slower, can't really comment from experience.

---

I've got the code to the point where it runs, and passes on small examples (17, for instance). However, it's been 8 or so minutes, and it's still running on my machine. I suspect that this algorithm, though simple, may not be the most effective, since it has to run through a lot of numbers a lot of times. (2 million tests on your first run, 1 million on your next, and they start removing less and less at a time as you go.) It also uses a lot of memory since you're, ya know, storing a list of millions of integers.

Regardless, here's my final copy of your code, with a list of the changes I made and why. I'm not sure that it works for 2,000,000 yet, but we'll see.

EDIT: It hit the right answer! Yay!

• Set memory_limit to -1 to allow PHP to take as much memory as it wants for this very special case (very, very bad idea in production scripts!)
• In PHP, use % instead of mod
• The inner and outer loops can't use the same variable; PHP considers them to have the same scope. Use, maybe, $j for the inner loop.
• To avoid having the prime strike itself off in the inner loop, start $j at $i + 1
• On the unset, you used $arr instead of $list ;)
• You missed a $ on the unset, so PHP interprets $list[j] as $list['j']. Just a typo.

I think that's all I did. I ran it with some progress output, and the highest prime it's reached by now is 599, so I'll let you know how it goes :)

My strategy in Ruby on this problem was just to check if every number under n was prime, looping through 2 and floor(sqrt(n)). It's also probably not an optimal solution, and takes a while to execute, but only about a minute or two. That could be the algorithm, or that could just be Ruby being better at this sort of job than PHP :/

Final code:

<?php

ini_set('memory_limit', -1);

    // The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
    // Additional information:
    //   Sum below 100: 1060 
    //        1000: 76127
    //  (for testing)

    // Find the sum of all the primes below 2,000,000.

    // First, let's set n = 2 mill or the number we wish to find
    // the primes under.

    $n = 2000000;

    // Then, let's set p = 2, the first prime number.

    $p = 2;

    // Now, let's create a list of all numbers from p to n.

    $list = range($p, $n);

    // Now the loop for Sieve of Eratosthenes.
    // Also, let $i = 0 for a counter.

 $i = 0;

 while($p*$p < $n)
  {
   // Strike off all multiples of p less than or equal to n

   for($j=$i+1; $j < $n; $j++)
    { 
     if($list[$j] % $p == 0)
     {
      unset($list[$j]);
     }
    }

   // Re-initialize array

   sort ($list);

   // Find first number on list after p. Let that equal p.

   $i = $i + 1;

   $p = $list[$i];
   echo "$i: $p\n";
  }

 echo array_sum($list);

    ?>