Ja, man würde vielleicht vermuten, dass es überhaupt keine Schwierigkeit ist, herauszufinden ob eine Zahl eine Primzahl ist oder nicht. Es soll jedoch Leute geben, die sich damit schwer tun (und zufälligerweise des öfteren neben mir in den Vorlesungen sitzen).
Deswegen von mir (auch wenn man dieses Problem wohl niemals rekursiv lösen würde) der entsprechende Source-Code dazu:
int isPrime(int num, int i) {
if (num == 0) return 0;
if (i*i > num) return 1;
if ((num%i) == 0) return 0;
return isPrime(num, (i+1));
}