0

I was trying to write a program that calculates prime number, an effective program.

i was trying some different ways to attack the issue.

def is_prime2(self, cand):
    for number in range(2, int(round(self.get_sqrt(cand)))):
        if cand % number == 0:
            return False
    return True

def is_prime(self, cand):
    return all(cand % number != 0 for number in range(2, int(round(self.get_sqrt(cand)))))

the is_prime2 method is much more faster than the is_prime method.

I'm trying to understand the reason for this difference, any ideas?

Also, is there a way to optimize the is_prime method?

omri_saadon
  • 10,193
  • 7
  • 33
  • 58
  • 2
    Possible duplicate of [Why is Python's 'all' function so slow?](http://stackoverflow.com/questions/11583869/why-is-pythons-all-function-so-slow) – Two-Bit Alchemist Jun 23 '16 at 20:08
  • @Two-BitAlchemist , Thanks for the link, it helped me. do you know whether it can be optimize? – omri_saadon Jun 23 '16 at 20:10
  • I think your first version is an optimization considering the necessity of constructing a generator just for all. If you already had the data in a list, it would be a different story. – Two-Bit Alchemist Jun 23 '16 at 20:11
  • It could simply be that `is_prime2` will return its answer before iterating through the whole `range()` whenever `cand` is not a prime. `is_prime` will run through the entirety of `range()` before returning, regardless of if `cand` is prime or not. – Will Jun 23 '16 at 20:13
  • @Will I'm pretty sure that when the if statement inside the all function is false than the iterations are stopped. – omri_saadon Jun 23 '16 at 20:16
  • 1
    @Will This is not true. `all` should short circuit as well. If `cand % number != 0` evaluates to `False` it should return immediately. – Brendan Abel Jun 23 '16 at 20:24
  • 2
    I see you're using python 2.7. Another optimization (not explaining why "all" is slow, explained above) would be to use xrange instead of range. For big numbers, it would avoid to allocate a list. In python 3, no need since range is now a generator. – Jean-François Fabre Jun 23 '16 at 21:03
  • @Jean-FrançoisFabre , the xrange is a great idea, it really fastened the run time in a significant way. please submit as an answer and i will accept it – omri_saadon Jun 23 '16 at 21:15
  • Wouldn't like to hammer as duplicate, But this is a highly related post [What is the difference between range and xrange functions in Python 2.X?](http://stackoverflow.com/q/94935) – Bhargav Rao Jun 23 '16 at 21:42
  • "*the is_prime2 method is much more faster than the is_prime method*" - can you support this assertion? In my testing, the two are identical in speed for `cand=2**31`. `is_prime()` is actually faster for `cand=2**31-1`. – Robᵩ Jun 24 '16 at 01:06

0 Answers0