Bueno, ahora pensé un poco mejor el código correspondiente.
Sea $n el número que tenés.
Código PHP:
# $actual es el número que estoy revisando (comienza por $n)
for ($actual = $n; $actual > 3; $actual--) {
for ($div = 2; $div <= ($n/2); $div++) {
if ( $actual % $div == 0 ) {
$divide = true;
break;
}
else {
$divide = false;
}
}
# si salí por el break, $divide = true;, si terminé el for, $divide = false
if (!$divide) {
$primos[(count($primos)] = $actual;
}
}
Teniendo una lista, podrías solamente revisar los primos que ya tenés (en vez de revisar todos los números) para ver si dividen a los que querés averiguar.
Saludos.