## Project Euler Problem 10 – Revisited (PHP)

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);

return \$this->arraySum;
}

{
\$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);

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;```
This entry was posted in PHP, Programming, Project Euler and tagged , , , . Bookmark the permalink.