Eu estava apenas pensando em um problema que não parece ser muito difícil, mas quando pensamos em fazê-lo de maneira ideal, isso se torna um bom problema. O problema é- Recebemos uma lista (matriz) de números e um número N. Temos que encontrar todos os divisores de N que não dividem nenhum número pertencente à lista. Eu resolvi isso com uma força bruta e uma abordagem pouco eficiente (mas não a melhor). Então, eu estou procurando uma abordagem que poderia ser a melhor na resolução deste tipo de problema. Tudo é em termos de inteiro (sem pontos flutuantes). Toda ideia é apreciada.

Minha abordagem para isso é que eu primeiro encontro todos os divisores do número N (sem nenhuma sobrecarga). Então, eu classifico a lista e os divisores na ordem inversa (separadamente). Agora, para cada divisor D, eu verifico se ele divide qualquer número na lista (a partir do elemento mais alto até um elemento que é> = o divisor D). Se se divide, então todos os divisores de D também devem se dividir. Então removo esses elementos da lista de divisores que também são os divisores de D (pode-se pensar em remover a interseção). Então, finalmente, o array esquerdo de divisores é o array requerido (de acordo com minha abordagem). Se alguém puder apontar qualquer falha ou falta de eficiência na minha abordagem, será apreciado. O valor máximo que pode estar presente na lista é 10 ^ 18.

Minha tentativa até agora em PHP:

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