CODEWITHSUNDEEP
pythonpython-2.7primes
Anshul Goyal
Anshul Goyal

Reputation: 76887

prime number generation code in python

I'm trying the following approach for generating primes:

primes = [2]
candidate = 3
MILLION = 1000000
while candidate < MILLION:
    if all(candidate % prime for prime in primes if prime**2 <= candidate):
        primes.append(candidate)
    candidate += 2

However, this is comparatively much slower than my previous code, where I wasn't using the all function, and was making the checks myself as below:

primes = [2]
candidate = 3
MILLION = 1000000
while candidate < MILLION:
    can_be_prime = True
    for p in primes:
        if p**2 > candidate:
            break
        elif candidate % p == 0:
            can_be_prime = False
            break
    if can_be_prime:
        primes.append(candidate)
    candidate += 2

While the second one gets over within 10 seconds, the first one takes forever to complete. Can someone help me understand why the first one starts outputting so slowly after the first 100000 numbers?

Upvotes: 1

Views: 240

Answers (2)

keajer
keajer

Reputation: 19

we can actually use 6n +/- 1 rule for generating primes. for example if you want to generate primes for a given number:

def primes(N):
    if N == 2:
        primes = [2]
    elif N >= 3:
        primes = [2, 3]
    else:
        return None
    for i in range(6, N):
        if i % 6 == 0:
            left = i - 1
            right = i + 1
            if all(left % p != 0 for p in primes):
                primes.append(left)
            if all(right % p != 0 for p in primes):
                primes.append(right)
    return primes

Upvotes: 0

poke
poke

Reputation: 387707

While your idea to shorten the code using that generator expression and any is good, they are not equivalent. In particular, in your longer solution, you are iterating the (sorted) list of primes and break the iteration as soon as you found a prime for which p ** 2 > candidate is true.

In your generator expression however, you try to make this check using x for p in primes if p ** 2 <= candidate. This is unfortunately not the same. Even if that check fails, the generator will still continue to iterate over the remaining primes, performing that p ** 2 for every single prime, on every iteration of the outer while loop.

You can verify that this is the problem, if you write it a bit differently:

def getPrimes (candidate):
    for p in primes:
        if p ** 2 > candidate:
            break
        yield p

while candidate < MILLION:
    if all(candidate % prime for prime in getPrimes(candidate)):
        primes.append(candidate)
    candidate += 2

So now, we’re using the same idea from the longer version and abort the iteration on primes as soon as we hit a prime for which p ** 2 > candidate is true. That way, we get the speed from the longer solution back.

Upvotes: 4

Related Questions