CODEWITHSUNDEEP
pythonpython-3.xoptimizationprimes
Bruce Dickie
Bruce Dickie

Reputation: 51

Why does my first function to find a prime number take so much longer than the other?

I have two functions: isPrime and alsoPrime. Both are meant to return True or False if the number (x) is a prime number. isPrime(x, pLis) takes on a growing list of numbers of primes and looks to see if x is a multiple of any primes. alsoPrime(x) searches all odd numbers starting at 3, ending at the root of x. I then use a for loop, starting at 3 and going up in intervals of 2.

I expected isPrime to be faster because it should skip numbers, i.e.:

isPrime -> 3, 5, 7, 11, 13, 17, 19

alsoPrime -> 3, 5, 7, 9, 11, 13, 15, 17, 19

But alsoPrime is immensely faster - 100X faster when searching through the first 1 000 000 numbers.

Can someone please explain why? Is it taking a lot of time to call the pLis each time?


def isPrime(x, pLis):
    for item in pLis:
        if x % item == 0:
            return False
    return True


def alsoPrime(x):
    for i in range(3, round(x**0.5)+1, 2):
        if x % i == 0:
            return False
    return True

Upvotes: 4

Views: 119

Answers (1)

mackorone
mackorone

Reputation: 1066

You're traversing through all of the primes you've discovered in isPrime when you really only need to traverse up to the square the candidate, like you do in alsoPrime. More iterations means slower code. Once quick way to verify this is to count the number iterations, like this:

def isPrime(x, pLis):
    for i, item in enumerate(pLis):
        if x % item == 0:
            print(f"{x} is not prime after {i} iterations")
            return False
    print(f"{x} is prime after {i} iterations")
    return True

Upvotes: 4

Related Questions