ProjectEuler.net - Solutions in PHP

project-euler.php

<?php

/**
 * Problem 10 - https://projecteuler.net/problem=10
 * Find the sum of all the primes below two million.
 */
function pe10() {
  // Remember all found primes in this array.
  $primes = array( 1 => 2 );
  $prime_count = 1;

  // First number to start with.
  $num = 3;

  while ( $num < 2000000 ) {
    // Check if $num is prime.
    $is_prime = true;

    // No need to check through all the numbers.
    $sqrt_num = sqrt( $num );

    // Make use of the primes we've already found.
    for ( $i = 1; $i < $prime_count && $primes[ $i ] <= $sqrt_num; $i++ ) {
      if ( 0 == $num % $primes[ $i ] ) {
        $is_prime = false;
        break;
      }
    }

    // Record $num if prime.
    if ( $is_prime ) {
      $primes[ ++$prime_count ] = $num;
    }

    // Next $num to check, ignore even numbers.
    $num += 2;
  }

  return array_sum( $primes );
}

/**
 * Problem 9 - https://projecteuler.net/problem=9
 * Find the product a*b*c of the only Pythagorean triplet for which a + b + c = 1000.
 */
function pe9() {
  for ( $a = 500; $a > 0; $a-- ) {
    for ( $b = 500; $b > 0; $b-- ) {
      for ( $c = 500; $c > 0; $c-- ) {
        if ( 1000 === ( $a + $b + $c ) && ( pow( $a, 2 ) + pow( $b, 2 ) ) == pow( $c, 2 ) ) {
          return $a * $b * $c;
        }
      }
    }
  }
}

/**
 * Problem 8 - https://projecteuler.net/problem=8
 * Find the thirteen adjacent digits in the 1000-digit number that have the greatest product.
 */
function pe8() {
  $str_big_num = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450';
  $digits = 13;
  $biggest_num = 0;

  // Move backwards through the numbers 1 by 1.
  for ( $i = strlen( $str_big_num ) - 1; $i >= $digits; $i-- ) {
    $cur_num = 1;

    // Multiply the 13 digits at the current position.
    for ( $d = 0; $d < $digits; $d++ ) {
      $cur_num *= intval( $str_big_num[ $i - $d ] );
    }

    // If the current number is bigger, save it.
    if ( $cur_num > $biggest_num ) {
      $biggest_num = $cur_num;
    }
  }

  return $biggest_num;
}

/**
 * Problem 7 - https://projecteuler.net/problem=7
 * Find the 10001st prime number.
 * (with help from http://paul-scott.com/nth-prime.php as my method was taking too long and timed out)
 */
function pe7() {
  $nth_prime = 10001;

  // Remember all found primes in this array.
  $primes = array( 1 => 2 );
  $prime_count = 1;

  // First number to start with.
  $num = 3;

  while ( true ) {
    // Check if $num is prime.
    $is_prime = true;

    // No need to check through all the numbers.
    $sqrt_num = sqrt( $num );

    // Make use of the primes we've already found.
    for ( $i = 1; $i < $prime_count && $primes[ $i ] <= $sqrt_num; $i++ ) {
      if ( 0 == $num % $primes[ $i ] ) {
        $is_prime = false;
        break;
      }
    }

    // Record $num if prime.
    if ( $is_prime ) {
      $primes[ ++$prime_count ] = $num;
      if ( $prime_count == $nth_prime ) {
        return $num;
      }
    }

    // Next $num to check, ignore even numbers.
    $num += 2;
  }
}

/**
 * Problem 6 - https://projecteuler.net/problem=6
 * Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
 */
function pe6() {
  $sum_of_squares = $squares_of_sum = 0;

  for ( $num = 1; $num <= 100; $num++ ) {
    $sum_of_squares += ( $num * $num );
    $squares_of_sum += $num;
  }
  $squares_of_sum *= $squares_of_sum;

  // Squares of sum is always bigger or equal.
  return $squares_of_sum - $sum_of_squares;
}

/**
 * Problem 5 - https://projecteuler.net/problem=5
 * Get the smallest positive number that is evenly divisible by all of the numbers from 1 to 20.
 */
function pe5() {

  // Get the factors of $num.
  function get_facts( $num ) {
    $num_orig = $num;
    $factors = array();

    // Try all the numbers up to $num.
    for ( $fac = 2; $fac <= $num; $fac++ ) {
      // Divide evenly by the current factor as long as we can.
      while ( 0 == $num % $fac && $fac != $num_orig ) {
        // Remember the number of factors.
        $factors[ $fac ] = ( isset( $factors[ $fac ] ) ) ? $factors[ $fac ] + 1 : 1;
        $num /= $fac;
      }
    }
    // If we have no factors till now this is a prime number, just add the number itself once.
    if ( empty( $factors ) ) {
      $factors[ $num_orig ] = 1;
    }

    return $factors;
  }

  $all_facts = array();
  for ( $i = 1; $i <= 20; $i++ ) {
    // Get all the prime factors.
    $facts = get_facts( $i );

    // Fetch the largest count of individual factors.
    foreach ( $facts as $fac => $cnt ) {
      if ( ! isset( $all_facts[ $fac ] ) || ( isset( $all_facts[ $fac ] ) && $all_facts[ $fac ] < $cnt ) ) {
        $all_facts[ $fac ] = $cnt;
      }
    }
  }

  $num = 1;
  // Multiply all factors together.
  foreach ( $all_facts as $fac => $cnt ) {
    $num *= pow( $fac, $cnt );
  }

  return $num;
}

/**
 * Problem 4 - https://projecteuler.net/problem=4
 * Find the largest palindrome made from the product of two 3-digit numbers.
 */
function pe4() {
  $pal = 0;

  // Loop down from 999 for both numbers.
  for ( $i1 = 999; $i1 > 0; $i1-- ) {
    for ( $i2 = 999; $i2 > 0; $i2-- ) {
      $num = $i1 * $i2;
      $num_str = strval( $num );
      // If it's a bigger palindrome than before, remember it.
      if ( $num > $pal && strrev( $num_str ) == $num_str ) {
        $pal = $num;
      }
    }
  }

  return $pal;
}

/**
 * Problem 3 - https://projecteuler.net/problem=3
 * Get the biggest prime factor of 600851475142.
 */
function pe3() {
  $num_orig = $num = 600851475142;
  $factor = 0;

  for ( $fac = 2; $fac <= $num; $fac++ ) {
    while ( 0 == $num % $fac && $fac != $num_orig ) {
      $factor = $fac;
      $num /= $fac;
    }
  }

  return $factor;
}

/**
 * Problem 2 - https://projecteuler.net/problem=2
 * Sum up all even numbers in the fibonacci sequence up to 4000000.
 */
function pe2() {
  $limit = 4000000;
  $prev = $cur = 1;
  $sum = 0;

  while ( $cur < $limit ) {
    if ( 0 == $cur % 2 ) {
      $sum += $cur;
    }
    $next = $prev + $cur;
    $prev = $cur;
    $cur  = $next;
  }

  return $sum;
}

/**
 * Problem 1 - https://projecteuler.net/problem=1
 * Sum up all numbers up to 1000 that are multiples of 3 and 5.
 */
function pe1() {
  $limit = 1000;
  $sum = 0;
  for ( $num = 0; $num < $limit; $num++ ) {
    if ( 0 == $num % 3 || 0 == $num % 5 ) {
      $sum += $num;
    }
  }
  return $sum;
}

?>