How can I optimize my sieve of Eratosthenes?

38 Views Asked by At

I made a sieve of Eratosthenes in python, and it can sort 10,000 numbers in 2 seconds. But I want to optimize this script further. Additionally, I would like to have a readout on what number it is sorting (e.g. "Removing multiples of 2 (4982)...") but this slows down performance too much to be a practical idea.

I tried optimizing by removing the temporary variable, but it took longer to get the index of the number in the primes list and use it instead. I also tried eliminating all uses of the sys and colorama module, but the impact on performance was negligible. Test data: 10,000 numbers without readout: 2.1s 10,000 numbers with readout: over 5 minutes

numbers is a list of all numbers (e.g. 2 to 10,000) i am using colorama and sys modules primes is also a list of numbers primetemp is temporary storage for a possible prime (number)

while len(numbers)>=1:
    primetemp=numbers[0]
    del numbers[0]
    sys.stdout.write("\033[F")
    print("Removing multiples of",str(primetemp)+"...", color.BLUE)
    for num in numbers:
        if num%primetemp==0:
            numbers.remove(num)
        else:
            continue
    primes.append(primetemp)
0

There are 0 best solutions below