Estaba pensando en un problema que no parece ser muy difícil, pero cuando pensamos hacerlo de manera óptima, se convierte en un problema bastante bueno. El problema es que se nos ha dado una lista (matriz) de números y un número N. Tenemos que encontrar todos los divisores de N que no dividen ningún número que pertenezca a la lista. Lo he resuelto con una fuerza bruta y un enfoque poco eficiente (pero no el mejor). Por lo tanto, estoy buscando un enfoque que podría ser el mejor para resolver este tipo de problema. Todo es en términos de entero (sin puntos flotantes). Cada idea es apreciada.

Mi enfoque para esto es que primero encuentro todos los divisores del número N (sin ninguna sobrecarga). Luego, ordeno la lista y los divisores en orden inverso (por separado). Ahora, para cada divisor D, verifico si divide algún número en la lista (desde el elemento más alto hasta un elemento que es> = el divisor D). Si se divide, entonces todos los divisores de D también deben dividirse. Luego elimino esos elementos de la lista de divisores que también son los divisores de D (se puede pensar que eliminan la intersección). Entonces, en última instancia, la matriz izquierda de divisores es la matriz requerida (según mi enfoque). Si alguien puede señalar cualquier falla o falta de eficiencia en mi enfoque, se agradece. El valor máximo que puede estar presente en la lista es 10 ^ 18.

Mi intento hasta ahora en 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>