finding the sum of all the primes below two million my code is slow

Question

I'm a beginner in python my code takes so much time just in finding the primes bellow 2 million he works fine with numbers like thousands but a million is a big number, anyone has an idea about whats can I do thank you in advance:

arr = list()
for i in range(2, 200000):
    for j in range(2, i + 1):
        if i % j == 0 and i == j:
            arr.append(i)
        elif i % j == 0 and i != j:
            break
        else:
            continue
print(arr)

Did you had a look at https://stackoverflow.com/questions/32542052/sum-of-primes-below-2-000-000-in-python?rq=1 — dreamcrash, Nov 27 '20 at 14:50
Are you not allowed to read about how to find primes efficiently? — superb rain, Nov 27 '20 at 14:50
The problem is you are using one of the slowest techniques to find primes below 2M. Check out: [Fastest way to list all primes below N](https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n) for faster options. — DarrylG, Nov 27 '20 at 14:57
@C14L Yes (at least for positive numbers). So? The way you said it sounds like that's wrong, and I don't think it is. — superb rain, Nov 27 '20 at 15:27

score 0 · Accepted Answer · answered Nov 27 '20 at 15:01

0

First of all, you could improve your list by using some logic. Exclude the number two and skip every even number:

for i in range(3, 200000, 2):

The same can be done in the second loop

You can also exclude all squares of the already found primes and so on

answered Nov 27 '20 at 15:01

Vlad

184
6

thanks bro he takes less time now – Abdelilah Zaidane Nov 28 '20 at 13:32

nenb · Answer 2 · 2020-11-27T16:02:31.783

0

The first step towards developing a more efficient algorithm would be to try the Sieve of Eratosthenes (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes):

limit = 200000
arr = list(range(limit))
# The algorithm starts at 2
for num in arr[2:]:
    if arr[num]:
        idx = 2 * num
        while idx < limit:
            arr[idx] = 0
            idx += num

primes = [elem for elem in arr if elem > 1]

edited Nov 27 '20 at 16:02

answered Nov 27 '20 at 15:19

nenb

63
5

Thanks for pointing this out. I've now edited my answer. – nenb Nov 27 '20 at 15:35
You can't use a slice of `arr` (which copies `arr`) without unnecessarily sieving a whole bunch of primes. You *want* the `if num:`, but you need to switch `for num in arr[2:]:` to something like `for num in itertools.islice(arr, 2, None):` so it sees a live view of your sieved `list` and the `if num:` can skip sieving when the number is already known non-prime. – ShadowRanger Nov 27 '20 at 15:39
@ShadowRanger Or they could've switched to `if arr[num]:`. – superb rain Nov 27 '20 at 15:40
@ShadowRanger That was very helpful, thanks! It's essentially what I wanted to do originally, but I didn't quite manage it. I have (again) edited my answer to reflect the suggestion from superb rain, because this is much closer to what I was trying to do originally. – nenb Nov 27 '20 at 16:05
@nenb thanks you that very help – Abdelilah Zaidane Nov 28 '20 at 13:30

finding the sum of all the primes below two million my code is slow

2 Answers2