[pplu]

Andres, estoy de acuerdo con tu solucion. Es más academica y menos retorcida que la mia, pero tambien es mas lenta. Te comento la mia, que al final queda asi:

function EsPrimo(Num: Integer): Boolean;
var
               temp, i, 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
while (i < (N shr 1)) 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;

y ya estaria la cosa resuelta

Comentarios: Si que se puede incrementar [i] de 2 en 2 porque antes ya has descartado todos los posibles multiplos de 2 con:
Enc := (n and 1) = 0

La mia es basicamente la tuya pero con las siguientes optimizaciones
- primero comprobar que sea multiplo de 2 (para asi poder incrementar i de 2 en 2)
- solo comprobar [i]s hasta n/2 (en ausencia de un sqrt(n)
- cambiar la condicion del while interno para que se ahorre una vuelta (y modificar la comprobacion de acuerdo con el cambio).