[pplu]

Y como ultima optimizacion que se me ocurre de momento es sacar una operacion que se mantiene invariante dentro del bucle

function EsPrimo(Num: Integer): Boolean;
var
               temp, i, hasta, integer;
               enc: boolean;
begin
Enc := (N and 1) = 0; //Aqui se dice si es divisible entre 2 y de paso se inicializa Enc
i := 3; // ya hemos comprobado los pares
hasta := N shr 1; // sacamos la condicion invariante
while (i < hasta) and not Enc do begin //Aqui vamos hasta n/2
	temp := N;
	while Temp >= i do Temp := Temp - i; //Aqui "dividimos"
	enc := (Temp = i); //Es divisible por i
	i := i + 2;
end;
return Enc;
end;

Sacando el (N shr 1) de la condicion del while, no se evaluará en cada vuelta del bucle, ahorrando asi, un poquito de tiempo (aunque los procesadores de hoy en dia ejecutan un shr en un ciclo...)
Algo es algo...