La lógica del programa?
Para que almacenar los números?

Partiendo de un número N lo divides por todos los números desde 2 hasta N-1, si en algún momento la división es 0, entonces el número no es primo y sales del bucle, si llega a N-1 y sigue "sobrando" (mod>0) entonces es primo 

Saludos

Bueno lo primero es sencillo, tal como dijo Novlucker pues irías dividiendo entre cada número menor que nuestro número, y si encuentras que ninguno lo divide, pues dirías que es primo.
Para saber los demás números primos inferiores, podrías hacer algo así como un doble bucle, por ejemplo:

$numero = 100;
 
// Bucle 1: Revisamos todos los numeros de 100 a 2
for( $maximo = $numero; $maximo > 2; $maximo--){
   //Bucle 2. Para cada numero, dividimos entre todos los inferiores a el.
   for( $actual = $maximo; $actual > 2; $actual-- ){
     if( $maximo % $actual == 0){
        echo "El numero ($maximo) es un numero primo.<br />";
        break;
     }
   }
}
 

Algo así es lo que se me ocurre ahora.