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

?>

Project Euler Problem 9

Project Euler Problem 9: Find the only Pythagorean triplet, {a, b, c}, for which a + b + c = 1000.

<?php


for ($m = 2 ; ; $m++)
{
  for ($n = 1 ; $n < $m; $n++)
  {
    $a = pow($m, 2)-pow($n, 2);
    $b = 2*$m*$n;
    $c = pow($m, 2)+pow($n, 2);
    if ($a+$b+$c == 1000) break 2;
  }
}
echo $a*$b*$c;

?>

Project Euler Problem 8

Project Euler Problem 8: Discover the largest product of five consecutive digits in the 1000-digit number.

<?php

$n = "73167176531330624919225119674426574742355349194934"
    ."96983520312774506326239578318016984801869478851843"
    ."85861560789112949495459501737958331952853208805511"
    ."12540698747158523863050715693290963295227443043557"
    ."66896648950445244523161731856403098711121722383113"
    ."62229893423380308135336276614282806444486645238749"
    ."30358907296290491560440772390713810515859307960866"
    ."70172427121883998797908792274921901699720888093776"
    ."65727333001053367881220235421809751254540594752243"
    ."52584907711670556013604839586446706324415722155397"
    ."53697817977846174064955149290862569321978468622482"
    ."83972241375657056057490261407972968652414535100474"
    ."82166370484403199890008895243450658541227588666881"
    ."16427171479924442928230863465674813919123162824586"
    ."17866458359124566529476545682848912883142607690042"
    ."24219022671055626321111109370544217506941658960408"
    ."07198403850962455444362981230987879927244284909188"
    ."84580156166097919133875499200524063689912560717606"
    ."05886116467109405077541002256983155200055935729725"
    ."71636269561882670428252483600823257530420752963450";

for ($i = $p = 0, $q = 1; $i < strlen($n)-4; $i++, $q = 1)
  for ($j = 0; $j < 5; $j++)
    $p = max($p, ($q *= $n[$i+$j]));
echo $p;

?>

Project Euler Problem 7

Project Euler Problem 7: Find the 10001st prime.

<?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 nth_prime($n)
{
  if ($n < 1) return false;
  if ($n < 3) return $n+1;
  for ($n -= 2, $p = 5 ; ; $p += 6)
  {
    if (is_prime($p) && !--$n) break;
    if (is_prime($p+2) && !--$n)
    {
      $p += 2;
      break;
    }
  }
  return $p;
}

echo nth_prime(10001);

?>

Project Euler Problem 6

Project Euler Problem 6: What is the difference between the sum of the squares and the square of the sums?

<?php

function diff_sumsqrs_sqrsums($n)
{
 for ($i = $s1 = $s2 = 1; $i < $n; 
   $i++, $s1 += $i, $s2 += pow($i, 2));
 return pow($s1, 2)-$s2;
}

echo diff_sumsqrs_sqrsums(100);

?>

Project Euler Problem 5

Project Euler Problem 5: What is the smallest number divisible by each of the numbers 1 to 20?

<?php

for ($n = 20; ; $n += 20)
{
 for($i = 20; $i > 10; $i--)
   if ($n%$i) continue 2;
 break;
}
echo $n;

?>

Project Euler Problem 4

Project Euler Problem 4: Find the largest palindrome made from the product of two 3-digit numbers.

<?php

$p = 0;
for ($i = 999; $i > 99; $i--)
 for ($j = $i; $j > 99; $j--)
  if (($n = $i*$j) == strrev($n))
   $p = max($n, $p);
echo $p;

?>

Project Euler Problem 3

Project Euler Problem 3: Find the largest prime factor of a composite number.

<?php

function lpf($n)
{
  if ($n < 2) return false;
  for ($p = 2; $p <= 3; $p++) 
    while (!($n%$p))
      if (($n /= $p) == 1) return $p;
  for ($p = 5, $d = 1; pow($p, 2) <= $n; 
    $p += 3-$d, $d *= -1)  
    while (!($n%$p))
      if (($n /= $p) == 1) return $p;
  return $n;
}

echo lpf(600851475143);

?>

Project Euler Problem 2

Project Euler Problem 2: Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million.

<?php

$s = $t = 2;
while (($t = round($t * pow((sqrt(5)/2)+0.5, 3))) 
  < 4000001) $s += $t; 
echo $s;

?>

Project Euler Problem 1

Project Euler Problem 1: Add all the natural numbers below one thousand that are multiples of 3 or 5.

// cheater...