一意的な除数を見つけるための最適なアルゴリズム

Question

私は単なる問題を考えていましたが、それほど難しくないと思っていましたが、最適に行うと考えるとかなり良い問題になります。問題は - 私たちは数のリスト（配列）と数Nを与えられました。リストに属する数を分けないNのすべての除数を見つけなければなりません。私は無理な力と少し効率的なアプローチで解決しましたが（最高のものではありません）。だから、私は、この種の問題を解決する上で最善の方法を探しています。すべては整数（浮動小数点数なし）の点であります。すべてのアイデアは高く評価されます。

これは私が最初に番号Nのすべての除数を（オーバーヘッドなしで）見つけることです。次にリストと除数を逆の順序で（別々に）ソートします。今、各除数Dについて、それがリスト内の任意の数を分けるかどうかをチェックする（最も高い要素から、> =除数Dまで）。分割すると、Dのすべての除数も除算する必要があります。次に、Dの除数でもある除数のリストからそれらの要素を削除します（交差点を削除すると考えることができます）。最終的に、除数の左の配列が必要な配列になります（私のアプローチに従う）。私のアプローチで誰かが何らかの欠陥や効率性の欠如を指摘できれば、それは感謝しています。リストに表示できる最大値は10^18です。これまでPHPで

私の試み： - あなたが与えられているリスト内の任意の単一のものより高いことを知っている値までのすべての数字をfatorizeするsieve of eratosthenesを行う

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

Answer 1

1つの明白な最適化は次のようです。今度は、そのリストから特定の数値のすべての要素を繰り返し処理できます。

あなたが次に行うのは、リストの各数字とその素因数pのそれぞれについて、Nで分けることができるまでpをNで分割する必要があります。あなたがした後、あなたが探している除数は残りの数のすべての除数です。

これが役に立ちます。