Verdad que es imposible el algoritmo numero primo sin usar ciclos, ni funciones.

[Ragnarok]

La máquina de Turing puede hacer cualquier cosa. ¿Tiene ciclos o funciones? Yo diría que no.

Lo único que hace falta es salto condicional.

[someRandomCode]

Es que caemos en lo mismo, un salto condicional hacia arriba que vuelve a repetirse, es un ciclo/bucle.

Porque? imaginense esto
Direccion            Codigo
000001              mov eax,5
000005              add eax,eax
000007              jnz 1

Esto es equivalente a:
for (int x=5;x==0;x++);

Y si quieren encapsularlo en una funcion recursiva, lo mismo, bueno, parecido, agrega un poco de codigo pero el concepto se queda en lo mismo.
Si por ejemplo con gcc/g++ le agregan un -funroll-all-loops para que trate de transformar los ciclos en algo lineal, van a ver que igual cosas como estas se repiten.

Si tenemos una funcion que es recursiva pasa lo mismo, salvo por, bueno, lo que implica como el paso de funciones y de mas, pero en si, la funcion esta siempre en el mismo lugar.

Aun con algunas formas de lenguajes orientados a objetos donde el sistema carga para dos objetos de la misma clase una sola vez la funcion se repite esto. Digo en algunos, porque no se en todos, pero en C++ si pasa, y se pueden fijar mirando el address de un puntero a funcion en dos funciones en dos objetos distintos del mismo tipo.

Me voy a sacar las ganas de preguntarlo en la facu, pero el debate esta bueno, y esta bueno ver sus opiniones, este foro da gusto cuando es asi