Si que se considera el 2 como primo en la sentencia
Enc := N And 1
Esto lo que hace es aplicar una máscara de bits al numero. Como en binario todos los numeros pares acaban en 0, Enc valdrá 0 si es par, y 1 si es impar.
y si quieres ahorrarte la mitad de vueltas en el bucle, puedes transformar:
while (i < N - 1) and not Enc do begin
en:
while (i < (N>>1)) and not Enc do begin
Esto divide N entre 2, ya que seguro que no habrá numeros que puedan dividir a n entre n/2 y n. El >> (right shift, o decalado) es un operador de C, seguro que delphi tambien lo tiene, pero no me acuerdo que pinta tenia. Es una division encubierta, pero válida.
Para hacerlo del todo chulo se podria ir hasta la raiz cuadrada de n (ya que hay una propiedad que dicta que n tiene todos los primos entre 2 y sqrt(n)). Pero no se hacer raices cuadradas de una forma mas o menos decente con las restricciones impuestas.
Seguiré pensando...
