**Problem 10**

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

**Script**

Execution Time: 22.5509 seconds

**Changes**

Basically, all math functions went into a class first off. Then I basically had the array populated and removed multiples of each number in the array starting with lowest value and going up from there.

I did run into an issue where I ran out of memory. This was solved by not including either even numbers or those divisible by 3 in the array. So the first number I worked with was 5 (4 was skipped because it was an even number.

I removed each multiple of 5 from the array of primes leaving 5 in the array. Once that was complete, I went on to the next value (7) and performed the same operations.

Doing the calculations in this manner saved approximately a full minute off the brute force method. I am sure there is an even faster way to calculate the value, but I am happy for now with the 22 seconds.

class.mathFunctions.php

class MathFunctions { public $v; private $arraySum; public function __construct() { $this->v = array(); $this->arraySum = 0; } /** * isPrime * * @param integer $n * @access public * @return void */ public function isPrime($n) { for ($x=2; $x<=sqrt($n); $x++) { if ($n%$x == 0) { return false; } } return true; } public function getPrimesBetween($a, $b) { if ($a == 1) $a++; if ($a == 2) { $this->v[$a] = 0; $a++; } if ($a == 3) { $this->v[$a] = 0; $a++; } for($x = $a; $x <= $b; $x++) { if ($x%2 != 0 && $x%3 != 0) { $this->v[$x] = 0; } } for($x = $a; $x <= $b/2; $x++) { $this->_removeNonPrimes($x); } } private function _removeNonPrimes($step) { $end = end($this->v); $end = key($this->v); for($x=$step*2; $x <= $end; $x += $step) { unset($this->v[$x]); } } public function getSumOfPrimesBetween($a, $b) { $this->getPrimesBetween($a, $b); array_walk($this->v, array($this, '_addArrayKeyValues')); return $this->arraySum; } private function _addArrayKeyValues($value, $key) { $this->arraySum += $key; } /** * isPandigital * * @param integer $n * @access public * @return boolean */ public function isPandigital($n) { if (is_array($n) === false) $n = str_split($n); $x = range(1, count($n)); $y = array_unique($n); sort($y); if (($x == $y) && (in_array(0, $x) === false)) { return true; } else { return false; } } /** * isPalindrome * * @param mixed $s * @access public * @return void */ public function isPalindrome($s) { if (is_array($s) === false) $s=str_split($s); $t = array_reverse($s); if ($s == $t) return true; else return false; } /** * isLychrel * * @param int $n * @param int $c * @access public * @return void */ function isLychrel($n, $c=0) { $x = str_split($n); $x = array_reverse($x); $x = join('', $x); $s = bcadd($x, $n); if ($this->isPalindrome($s) === true) { return false; } elseif($c >= 50) { return true; } return $this->isLychrel($s, ++$c); } }

p10.php

require_once 'class.mathFunctions.php'; $number = new MathFunctions; echo $number->getSumOfPrimesBetween(1, 2000000); echo PHP_EOL;