Trying to print all prime numbers below two million-CodePudding

I was trying to print the sum of every prime number below two million, it should print 142913828922 but it´s printing 142913827513. How can I get the right number?

This is my code:


def SumOfPrimesBelow(num):
    contador = 0
    primos = []
    for c in range(1, int(math.sqrt(num))):
        for c2 in range(1, c):
            if c % c2 == 0:
                contador  = 1
        if contador == 1:
            primos.append(c)
        contador = 0
    primos2 = []
    for c in range(1, num):
        for num5 in primos:
            if c != num5:
                if c % num5 == 0:
                    break
        if c % num5 == 0:
                continue
        if c != 1:
            primos2.append(c)
    cont = 0
    for num in primos2:
        cont  = num
    return cont


print(SumOfPrimesBelow(2000000))

CodePudding user response：

Your answer is off by 1409, the prime number that you code failed to capture in primos2 due to the following reason:

After this loop

for num5 in primos:
    if c != num5:
        if c % num5 == 0:
            break

num5 has a value of 1409 (the last element of primos). Therefore, for loop c = 1409, the continue line will be executed and 1409 will not be appended to primos2.

This can be resolved by changing the line if c % num5 == 0: to if c % num5 == 0 and c != num5:

CodePudding user response：

When you write the two lines of code:

if c % num5 == 0:
    continue

You're actually outside of the for num5 in primos: loop.

So what do you expect the value of num5 to be in that case, and what is the logic of these two lines?

If you simply remove these two lines, your code should work as expected.

But actually, you can make your code even simpler and more efficient by starting the big loop at int(math.sqrt(num)) instead of at 1. Indeed, you've already computed the prime numbers below this threshold, so there is no need to compute them again.

Also, since you're only interested in the sum, you don't need to store the whole list primos2. You can add the prime numbers to cont directly.

I've also slightly modified your code to use math.isqrt instead of int(math.sqrt(...)); and to use all(...) and any(...) which increases readability and avoids break and continue. In general I very strongly discourage the use of break and continue. For-loops are easy to read because they have a straightforward logic. Breaking that logic with break is deceptive for people who read your code.

Finally:

from math import isqrt

def SumOfPrimesBelow(num):
    primos = []
    threshold = isqrt(num)
    for c in range(2, threshold):
        if not any(c % c2 == 0 for c2 in range(2, c)):
            primos.append(c)
    cont = sum(primos)
    for c in range(threshold, num):
        if all(c % prime != 0 for prime in primos):
            cont  = c
    return cont

print(SumOfPrimesBelow(2000000))

Output:

142913828922