2

new to Python here. I am trying to understand how this function works to check prime numbers:

from itertools import count, islice
from math import sqrt
def is_prime(n):
    if n < 2: return False
    return all(n%i for i in islice(count(2), int(sqrt(n)-1)))

From what I understand you can check factors up to and including the square root of n, so why is this only testing up to sqrt(n)-1? I'm also not clear on the return all part for the function. n%i returns an int, the remainder. So why does this expression evaluate as a bool? Any pointers on this would be great. thanks!

Kex
  • 8,023
  • 9
  • 56
  • 129
  • Take a look at the docs for [all()](https://docs.python.org/3/library/functions.html#all). – PM 2Ring Aug 29 '15 at 08:33
  • @PM2Ring Return True if all elements of the iterable are true. But the elements of the iterable are ints not bools. – Kex Aug 29 '15 at 08:35
  • 1
    0 is cast to False, and any other number is cast to True in python by default. – Igor Pejic Aug 29 '15 at 08:36
  • @Igor thanks, got it – Kex Aug 29 '15 at 08:38
  • The neat thing about using a generator expression like this in the call to `all()` is that `all()` short-circuits, so `all()` will stop calling the generator as soon as it detects that a False-ish value has been generated. In other words, the loop stops as soon as a factor is found. Similar remarks apply to `any()` - a generator expression inside `any()` will stop as soon as a True-ish value is produced. – PM 2Ring Aug 29 '15 at 08:44
  • @PM2Ring that is nice! Thanks for elaborating. – Kex Aug 29 '15 at 08:55
  • Please check this. I am not sure if this answers your question but this is probably the best way https://stackoverflow.com/a/71438297/3204942 – Gary Mar 11 '22 at 12:16

2 Answers2

4

Because the second argument to islice is a count, not the value to stop on.

This would be far better written with xrange(2, int(sqrt(n))+1)

The plus one here is to make the range inclusive at both ends, which xrange normally is not.

Eric
  • 95,302
  • 53
  • 242
  • 374
  • Or in Python 3, `range(2, int(sqrt(n))+1)`, although I prefer to save a `math` module call and do `n**0.5` rather than `sqrt(n)`. – PM 2Ring Aug 29 '15 at 08:47
1

  1. The function is infact checking for sqrt(n). Because islice(count(2), sqrt(n)-1) means count sqrt(n)-1 numbers starting from 2. While checking for prime numbers, it is enough to check from 2 to it's square root because even if there is a factor greater than square root, it will have a corresponding factor less than the square root. Using int(sqrt(n)) here, would mean we are checking an additional number - no harm but unnecessary. Using int(sqrt(n) - 1) means we do only the comparisons that are necessary.

  2. all() will return true, if all elements of the iteration evaluates to true. In python 0 evaluates to false. Which means, if for any number between 2 and sqrt(n), remainder of integer division is 0, the all() will return false. This is correct because if there is a factor, the number is not prime. If for 2 to sqrt(n), the remainder of integer division is never 0, then the number is prime - all() will return true as there are no zeroes in the iterations.

https://docs.python.org/2/library/itertools.html#itertools.islice

manojtc
  • 562
  • 3
  • 10
  • Excellent, thanks for the detailed answer. Understand it clearly now. – Kex Aug 29 '15 at 08:43
  • 1
    This is wrong - the code is not checking every number between 2 and n-1 – Eric Aug 29 '15 at 08:49
  • @Eric yes. It's actually because the sequence starts at 2 not 1 and so have to subtract 1. e.g. checking 16 [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]. sqrt is 4. First 4 terms are 2,3,4,5 we are including 5 in which we don't need hence sqrt(n)-1. – Kex Aug 29 '15 at 09:19
  • @Eric you're right. I have corrected my answer. Thanks for noticing. – manojtc Aug 29 '15 at 09:20