Home > Back-end >  check if number is prime using recursion with only one parameter in c language
check if number is prime using recursion with only one parameter in c language

Time:05-22

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.

CodePudding user response:

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.

  • Related