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

1

エラトステネスのふるいのこのPHP実装を使用できます。

そしてこれも。

そしてこれ。

この質問を見てください。

于 2012-04-08T10:20:12.327 に答える