check if number is prime using recursion with only one parameter in c language

Advertisements

I’ve got a task in my lesson to write a function that will check if a number is prime, it will return 1 if it is and 0 if it is not and all of that to do recursively. the function will look like that :int isPrime(int num);
I’ve tried everything and searched everywhere and came to the conclusion that it’s possible only with static int which I did not learn yet so can’t use it or with two parameters.
does anyone know if there is a way to solve it with only one parameter ad no static int?
thanks.

>Solution :

This was a trick question: you are supposed to use recursion, but unless you are barred from using loops, a classic solution with a for loop can be made to comply with the recursion requirement.

Here is a function isPrime that has a single argument and uses a classic loop and recursion to test prime divisors:

int isPrime(int n) {
if (n <= 1)
return 0;
if (n % 2 == 0)
return n == 2;
for (int p = 3; p * p <= n; p += 2) {
if (isPrime(p) && n % p == 0)
return 0;
}
return 1;
}

The above code only performs the modulo operation for prime divisors. It is a false optimisation because it is actually more costly to determine if p is prime with a recursive call than to compute n % p.