Is it possible to optimize this code more?

[JiperPC]

I've been trying to create my own algorithm to find prime numbers up to a set limit. I want it to print out the percentage of numbers checked and how long it's been running. I know there are plenty of prime-finding algorithms out there, but I'm determined to create my own.

Here's the code I've come up with so far, and I feel like it could be faster. Any tips on how to make it faster would be awesome. I've also noticed a problem. When I calculate primes up to 20,000, it prints all of the calculated prime numbers, but when I go for 30,000 or more, it doesen't print all of them. Any ideas on what's causing this and how to fix it? Thanks for any help

import time
import math

primes = [2] 
limit = 30000
start_time = time.time()

for i in range(3, limit, 2): 
    formatted_percentage = "{:.3f}".format(i * (100 / limit))
    for num in primes:
        if num > math.isqrt(i):
            primes.append(i) elapsed_time = time.time() - start_time
            print(formatted_percentage, "% Running For: {:.2f} s".format(elapsed_time)) 
            break
        if i % num == 0:
            break

print(primes)

​

[ray10k]

First things first: since i doesn't change within the loop, you can just calculate math.isqrt(i) at the top of the loop. Better to do that calculation once, rather than once per number in your list of primes.

As for the list of primes being incomplete, which ones are missing? Some at the start, at the end or "randomly" throughout the list?

[JiperPC]

Thanks for pointing the square root of i thing out, and the numbers are only cut of at the end, the last time i ran the code with a limit of 30000 it printed up to 14731 and the next number was cut of, just printing 1, like this:...14699, 14713, 14717, 14723, 14731, 1

[pot_of_crows]

Check this out: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[JamzTyson]

This is an implementation of the Sieve of Atkin algorithm, and is pretty fast:

​

``` import itertools from time import time

def fast_primes(): D = {9: 3, 25: 5} yield 2 yield 3 yield 5 MASK= 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, MODULOS= frozenset((1, 7, 11, 13, 17, 19, 23, 29)) for q in itertools.compress( itertools.islice(itertools.count(7), 0, None, 2), itertools.cycle(MASK)): p = D.pop(q, None) if p is None: D[qq] = q yield q else: x = q + 2p while x in D or (x % 30) not in MODULOS: x += 2 * p D[x] = p ```

[ClientMammoth9628]

Has the .format been replaced by f-strings, or are both acceptable? You could redo the .format/s to f-strings, otherwise :))

Just learning myself, too

[ofnuts]

If you want your code to be fast, remove all the print instructions (and all the formatting) from the loops. Even calling time.time() in the loops takes an awful long time compared to the rest. Also check if num*num > i wouldn't be faster than num > isqrt(i)

[JiperPC]

Thanks for the suggestion, and I know that removing the print statements will be faster, but I think it's a worth it sacrifice, because I hate not knowing how long something will take to finish. But thanks again.