CODEWITHSUNDEEP
php
Umair Abid
Umair Abid

Reputation: 1463

Calculating Highly divisible triangular number with PHP

I am trying to resolve project euler problem no 12 with PHP but it is taking too much time to process. I came across with similar processing problems of PHP while solving previous problems and I had to solve them in C++ just to test whether my approach is correct or not. I want to know whether there is something wrong with my approach or somehow I can do something to make processing fast. Here is the code of my solution which works well for the triangle having 360 divisors. The link of problem is http://projecteuler.net/problem=12 and here is my code

<?php 
    set_time_limit(0);
    ini_set('memory_limit', '1G');

    $triangles = array(0);
    $count = 1;
    $numOfDivisiors = 0;
    $lastTriangle = 0;

    while($numOfDivisiors < 500){
        $triangle = (int) $lastTriangle + (int) $count;
        $factors = getFactors($triangle);
        //$triangles[] = array('triangle' => $triangle, 'factors' => $factors, 'factorsCount' => count($factors));
        $triangles[] = array('triangle' => $triangle, 'factorsCount' => count($factors));

        $lastTriangle = $triangle;
        $numOfDivisiors = count($factors);
        $count++;
        //echo '<pre>'; print_r(array('triangle' => $triangle, 'factorsCount' => count($factors), 'count' => $count)); echo '</pre>';
    }

    echo $numOfDivisiors; exit;

    /**
    for($i = 0 ; $i < 10 ; $i++){

    }
    **/
    //echo '<pre>'; print_r($triangles); exit;

    function getFactors($number){
        $factors = array();
        $break = false;
        $count = 1;
        while($break != true){
            $remainder = $number % $count;
            if($remainder == 0){
                $factors[] = $count;
            }
            //echo $count." ".$number; exit;
            if($count == $number){
                $break = true;
            }
            $count++;
        }
        return $factors;
    }
?>

Upvotes: 1

Views: 1359

Answers (2)

exussum
exussum

Reputation: 18568

use some maths.

triangle numbers can be generated by

n(n+1) /2

and that if you can find the prime factors, Adding 1 to their powers and multiplying together gives the number of divisors.

My PHP solution takes around 4 seconds and i think i can speed that up also

Upvotes: 2

Jackson
Jackson

Reputation: 5657

There are several ways to speed up your solution. The first one I'd point you at is the following:

if a * b = c then both a and b are factors of c

One of a and b will be <= to the square root of c

this should help speed up your solution

Upvotes: 0

Related Questions