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

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

Want to improve this question? Guide the asker to update the question so it focuses on a single, specific problem. Narrowing the question will help others answer the question concisely. You may edit the question if you feel you can improve it yourself. If edited, the question will be reviewed and might be reopened.

Closed 3 years ago.

Improve this question

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.

static int IsPrime(int n) { if (n < 2) return 0; for (int d = 2; d*d <= n; ++d) if (n % d == 0) return 0; /* Look, recursion! */ return !IsPrime(1); } — Eric Postpischil
– Eric Postpischil, Commented May 21, 2022 at 23:35
How big is the number? There's probably lots of unused bits in that single parameter you could totally use for other things. — Retired Ninja
– Retired Ninja, Commented May 21, 2022 at 23:37
See the recent similar question: stackoverflow.com/questions/72061248/… — Craig Estey
– Craig Estey, Commented May 21, 2022 at 23:47
include stdbool.h and use bool isPrime(int num) and return true or false — Goswin von Brederlow
– Goswin von Brederlow, Commented May 22, 2022 at 3:36

chqrlie · Accepted Answer · 2022-05-21 23:55:37Z

1

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.

edited May 21, 2022 at 23:55

answered May 21, 2022 at 23:40

chqrlie

152k12 gold badges145 silver badges231 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Goswin von Brederlow Over a year ago

How is that the answer? If you remove the recursive call the function still works, it's even faster.

chqrlie Over a year ago

@GoswinvonBrederlow: sure, it is quite common to optimize code by simply removing redundant or useless code :) If you have a better solution with recursion, I am curious to see it. This silly answer to a trick question can prompt a discussion about premature optimisation, which might be the purpose.

Goswin von Brederlow Over a year ago

I don't think the question makes any sense. You can't do it without cheating: static variable, global variable, putting multiple numbers into the int, binding in a lambda. You need something to hold a second argument to turn your for loop into a recursion.

chqrlie Over a year ago

@GoswinvonBrederlow: I agree, and this question is close to a recent duplicate... Maybe the teacher's agenda is to deter students from using recursion to no avail.

Goswin von Brederlow · Accepted Answer · 2022-05-22 07:53:57Z

0

So here is my solution to this questionable assignment. It contains only functions taking one int argument and uses recursion and no loop:

#include <iostream>
#include <functional>

std::function<bool(int)> isPrime(int x) {
    return [x](int p) {
        if (x <= 2) return true;
        return (p % (x - 1) != 0) && (isPrime(x - 1)(p));
    };
}

int main() {
    if (isPrime(19)(19)) std::cout << "is prime" << std::endl;
}

answered May 22, 2022 at 7:53

Goswin von Brederlow

12.4k2 gold badges27 silver badges47 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

4 Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Linked

Related