Project Euler Problem 10

Project Euler Problem 10: Calculate the sum of all the primes below two million.

Brute force (optimized to only look at 6n±1)...

<?php

function is_prime($n)
{
  if ($n < 5) return ($n == 2 || $n == 3);
  for ($p = 2; $p <= 3; $p++)
    if (!($n%$p)) return (($n /= $p) == 1);
  for ($p = 5, $r = floor(sqrt($n)); $p <= $r; $p += 6)
  {
    if (!($n%$p)) return false;
    if (!($n%($p+2))) return false;
  }
  return true;
}

function sum_primes($l)
{
  if ($l < 2) return 0;
  if ($l < 3) return 2;
  if ($l < 5) return 5;
  for ($s = $p = 5; $p <= $l; $p += 6)
  {
    if (is_prime($p)) $s += $p;
    if (is_prime($p+2) && $p+2 <= $l)
      $s += $p+2;
  }
  return $s;
}

echo sum_primes(2000000); // time 6.126s

?>

Since we know the upper limit, we can sieve...

<?php

function prime_sieve($l)
{
  $b = ($l-1)/2;
  $p = array_fill(1, $b, 0);
  $c = (floor(sqrt($l))-1)/2;
  for ($i = 1; $i <= $c; $i++)
    if (!$p[$i])
      for ($j = 2*$i*($i+1); $j <= $b; $j += 2*$i+1)
        $p[$j] = 1;
  return $p;
}

function sum_prime_sieve($l)
{
  $b = count($p = prime_sieve($l));
  for ($i = 1, $s = 2; $i <= $b; $i++)
    if (!$p[$i]) $s += (2*$i+1);
  return $s;
}

echo sum_prime_sieve(2000000); // time 1.042s

?>