Primes under 2 Million

Question

I made this code for project Euler (its in the first 100, so allowed to ask here I believer), but it is veeery slow. I believe it should work, but I would like to make it go faster. I feel like it would take an hour to finish. Here is the code in python.

guess=2
prime=True
total=0
while guess<2_000_000:
    prime=True
    for i in range(2, guess):
        if guess%i == 0:
            prime=False
    if prime:
        total+=guess
    guess+=1
print(total)

You're incrementing your guess by 1, but you know that primes are 1,2,3,5,7,11, etc. so no need to increment by 1. As a starter you can remove all even numbers, so instead of incrementing by 1 you could increment by 2 (starting from an odd number). This will speed up at least by a factor of 2 your computation. Then I'm sure you can think of smarter ways to make your increment dynamic ;) Same for your for loop, it can be optimised. — BourbonCreams, Jul 22 '20 at 17:29

score 0 · Answer 1 · answered Jul 22 '20 at 17:28

Few ideas -

Once you find out that a number is not prime you can break the loop (after the if in the inner loop)
It is sufficient for the inner loop can run until the square root of guess and not until guess.

I think those ideas would speed your code significantly

Primes under 2 Million

1 Answers1