0

あまり難しくないように見える問題を考えていたところですが、最適に行うことを考えると、かなり良い問題になります。問題は、数値のリスト (配列) と数値 N が与えられていることです。リストに属する数値を割り切らない N のすべての約数を見つけなければなりません。私は力ずくで少し効率的なアプローチで解決しました（ただし、最善のアプローチではありません）。だから、私はこの種の問題を解決するのに最適なアプローチを探しています.すべては整数（浮動小数点なし）の観点からです. すべてのアイデアが高く評価されています。

これに対する私のアプローチは、最初に数 N のすべての約数を (オーバーヘッドなしで) 見つけることです。次に、リストと約数を逆の順序で (別々に) 並べ替えます。ここで、除数 D ごとに、リスト内の任意の数を除算するかどうかを確認します (最高の要素から除数 D より大きい要素まで)。割り切れる場合、D のすべての約数も割り切らなければなりません。次に、D の約数でもある約数のリストからそれらの要素を削除します (交差を削除すると考えることができます)。したがって、最終的には、除数の左の配列が必要な配列です (私のアプローチによると)。誰かが私のアプローチの欠点や効率の欠如を指摘できれば幸いです。リストに表示できる最大値は 10^18 です。

PHPでのこれまでの私の試み:

while($div=each($divisors))
{
$i=0;
$divisor=$div['key'];
//echo "divisor is $divisor\n";
while((int)$unfriendly[$i]>=$divisor)
{//echo "aya\n";
    if(!((int)bcmod($unfriendly[$i],$divisor)))
    {//echo "ayeea\n";
        $divisors_of_divisor=divisors_of_a_number($divisor);
        //print_r($divisors_of_divisor);
        //print_r($divisors);
        foreach($divisors_of_divisor as $d)
        unset($divisors[$d]);
        //print_r($divisors);
        break;
    }
    ++$i;
}
 }
echo sizeof($divisors);
function divisors_of_a_number($n)//returns all the divisors of a number in an unsorted array
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[]=$i;
    if($i!=$s)
    $a[]=$n/$i;
}
++$i;
}
return $a;
}
function divisors_of_a_number_as_keys_of_array($n)//returns all the divisors of a number in an unsorted array as keys
{
$i=1;
$s=sqrt($n);
while($i<=$s)
{
if(!($n%$i))
{
    $a[$i]=1;
    //if($i!=$s)
    $a[$n/$i]=1;
}
++$i;
}
return $a;
}
4

1 に答える 1

0

明らかな最適化の 1 つは次のとおりです。エラトステネスのふるいを行い、与えられたリスト内の任意の 1 つよりも高いことがわかっている値まですべての数値を因数分解します。これで、そのリストから特定の数値のすべての因数を反復処理できます。

次に行うことは、リストの各数値とその素因数 p ごとに、N が p で割り切れるまで N を p で割ります。それを行った後、探している除数は残りの数のすべての除数です。

お役に立てれば。

于 2012-04-08T07:43:24.357 に答える