Project Euler Problem 10 – Revisited (PHP)

Author

Joseph

Created

October 27, 2011

Reading time

5 min

Views

314

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;