あまり難しくないように見える問題を考えていたところですが、最適に行うことを考えると、かなり良い問題になります。問題は、数値のリスト (配列) と数値 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;
}