Question

Can you help me with this build a recursive algorithm that checks if a number n>=2 is prime or not (pascal) @Computer Science

Answer 1

don't know pascal but:

define function isPrime(x, n = 2):
if n equals x:
return True
if x mod n equals zero:
return False
return True and isPrime(x, n + 1)

Answer 2

the exercise had this note (base on the idea that we must check numbers from 2 to sqrt(n). if mod =o that means that the numbers is not prime if mod different from 0 that means that we must check next numbers (i don't know if this note is correct ))

Answer 3

in my pseudocode - x mod n == 0 is the prime test
to limit the number of tests you only have to test for n less than or equal to sqrt(x)


define function isPrime(x, n = 2):
if n > sqrt(x):
return True
if x mod n equals zero:
return False
return True and isPrime(x, n + 1)

Answer 4

n>=2 and we check from 2 to sqrt(n) why is if n > sqrt(x): and why not
if n < sqrt(x):

Answer 5

Because isPrime is continuing to check the mod until n > sqrt(x). If isPrime has not found a (x mod n == 0) by the time n > sqrt(x), then n is a prime number.

Answer 6

thank you both of you

Answer 7

limiting n to sqrt(x) is an optimization. if you tested all the way up to x-1 it would still work - but you would just be wasting time.

Answer 8

http://codepad.org/n8IBdlVx
When I write recursive functions I usually need them to take more arguments than the real function would take. So I usually define a separate recursive helper function, and have the real function delegate to that one (and set up the extra variables). Also, even though the recursive helper function will only be used by the one real function I like it to have a descriptive name. That way, as I'm reading the code for the recursive call, it still makes sense in English.

True, it's not as efficient as it could be, because it checks divisors greater than sqrt(n), but that's not the point of this assignment. (If it was, then you sure as heck wouldn't want to do it recursively.) You're supposed to learn how to write a function that calls itself. As such, I think this is a bad example of how to use recursion. The concept of primality doesn't have a recursive definition. If it did you'd be able to say something like
isPrime(n) = (check n) or isPrime(n-1)
But that's now how primeness works. Maybe there's a better way to phrase the problem to make the recursive solution more natural. I don't know.

Answer 9

well in fact i thought that this is bad example of using recursive algorithms because recursive algorithms must have "basic case" and in this case it hasn't so i'll try to explain it with words

Answer 10

The base case is x = 2, which is sort of implied in bwCA's function call because he begins checking for divisors at the first prime. It might be better to assert that x is >= 2.

Answer 11

there are two base cases:
1- n equals x
2- x mod n equals zero (actually an optimization)

you could rewrite it for one base case as:

define function isPrime(x, n = 2):
if n equals x:
return True
return (x mod n does not equal zero) and isPrime(x, n + 1)