Python built-in functions such as any [duplicate]

Question

I wrote a function to know whether a number is prime in Python (using Python 3.8.1 in this case). See is_prime_v1 below. Then I thought of trying a v2 by using the any built-in function, see is_prime_v2 below. I was curious to know the time difference between v1 and v2, and with the code below I get the following output on my computer:

v1: 5.224290132522583
v2: 7.654775142669678

Which surprises me. I would have assumed that making use of any would take about the same time or even be faster. But here it's slower, a guess could be that it's due to the function call to any itself, but I'm unsure. Maybe someone with deeper Python knowledge could explain why?

from time import time
from math import sqrt


def is_prime_v1(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    for i in range(3, int(sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True


def is_prime_v2(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    return not any(n % i == 0 for i in range(3, int(sqrt(n)) + 1, 2))


if __name__ == '__main__':
    RANGE_SIZE = 2000000

    t = time()
    for i in range(RANGE_SIZE):
        is_prime_v1(i)
    print('v1:', time() - t)

    t = time()
    for i in range(RANGE_SIZE):
        is_prime_v2(i)
    print('v2:', time() - t)

generator expressions n % i == 0 for i in range(3, int(sqrt(n)) + 1, 2) slow things down. They are essentially equivalent to your regular loop but with overhead — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Mar 14, 2021 at 22:31

TheEagle · Accepted Answer · 2021-03-14 22:37:53Z

0

When using solution 2, you have 2 for loops instead of one in your solution 1:

One in the any function (it needs to loop over the values you are giving it)

One as argument to the any function, which is equivalent to your original for loop.

Additionally, as @juanpa.arrivilaga pointed out, you are creating a generator object, which creates additional overhead.

answered Mar 14, 2021 at 22:37

TheEagle

6,0053 gold badges16 silver badges45 bronze badges

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

3 Comments

juanpa.arrivillaga Over a year ago

"When using solution 2, you have 2 for loops instead of one" No? Why do you say that?

TheEagle Over a year ago

@juanpa.arrivillaga well, one for loop in the anyfunction itself, an the other for loop is the one from solution 1 in one line,

TheEagle Over a year ago

@juanpa.arrivillaga any does use a loop, doesn't it ?

Collectives™ on Stack Overflow

Python built-in functions such as any [duplicate]

1 Answer 1

3 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Linked

Related