1

我正在尝试使用 PHP 解决项目 euler 问题 12，但处理时间太长。我在解决以前的问题时遇到了类似的 PHP 处理问题，我不得不用 C++ 解决它们，只是为了测试我的方法是否正确。我想知道我的方法是否有问题，或者我可以做些什么来加快处理速度。这是我的解决方案的代码，它适用于具有 360 个除数的三角形。问题的链接是http://projecteuler.net/problem=12这是我的代码

<?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;
    }
?>
4

2 回答 2

2

使用一些数学。

三角形数可以由

n(n+1) /2

如果你能找到素因数，将它们的幂加 1 并相乘得到除数的数量。

我的 PHP 解决方案大约需要 4 秒，我想我也可以加快速度

于 2013-07-01T19:53:32.840 回答
0

有几种方法可以加快您的解决方案。我要指出的第一个是以下内容：

如果 a * b = c 那么a 和 b都是c 的因数

a 和 b 之一将 <= c 的平方根

这应该有助于加快您的解决方案

于 2013-06-17T13:32:31.270 回答