1

PHP でプロジェクト オイラーの問題番号 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 に答える