Reputation: 124
I have this code:
def isPrime(nr):
"""
Verify if a number is prime
nr - integer number, nr>1
return True if nr is prime, False otherwise
"""
div = 2 #search for divider starting from 2
while div<nr and nr % div>0:
div=div+1
#if the first divider is the number itself
#then the number is prime
return div>=nr
It's not written by me, so I'm trying to understand how the algorithm works, apparently it is using a form of divide & conquer.
What I don't understand is what the last line does:
return div>=nr
Upvotes: 0
Views: 80
Reputation: 42421
Python comes with an interactive environment where you can experiment with simple scripts like the one you posted.
$ python # From the command line just run 'python'.
>>> nr = 13 # Type in some code.
>>> div = 2
>>> while div<nr and nr % div>0:
... div=div+1
... # Press 'Enter' here to end the indentation.
>>> div # Type a variable to see what it equals.
13
>>> nr # Again.
13
>>> div>=nr # Ahhh, the answer to your question.
True
>>>
Upvotes: 0
Reputation: 510
The algorithm is just testing every number from 2 up to nr
to test if nr
is divisible by the number. If at any point it is (nr % div
is equal to 0), the loop breaks. This will return False if div < nr
. If the loop gets to nr
, then we know there is no number between 2 and nr
that divides the nr
and so it is prime, returning True. The other answer explains how the return works.
Definitely not using divide & conquer.
Upvotes: 0
Reputation: 141998
return div>=nr
...is equivalent to...
if div >= nr:
return True
else:
return False
That is, it is not "returning a comparison" but returning the result of a comparison.
Upvotes: 3