Search code examples
pythonperformanceexecution

Python is taking a very long time to execute code

I'm using PyCharm community 2018. I'm trying to find the sum of prime numbers from 1 to two million and this is my code.

primes = [x for x in range (1,2000000) if all (x%y!=0 for y in range (2,x))]
total = 0
for x in primes:
    total = total + x
print (total)

It's been 20 minutes and I've still got no output. Do you have any suggestions to make it run faster or is my method wrong?

Solution

  • This is most likely because your method to find primes is inefficient and your range is too large.

    Your algorithm is a brute force way of finding prime numbers and it's time complexity is O(n²). If you time your algorithm for smaller numbers you will see that as you increase n, time taken does not increase linearly, but is in fact quadratic. 

    +--------+---------------+
|   n    | time(in sec)  |
+--------+---------------+
| 1000   |  0.007979     |
| 2000   |  0.038865     |
| 5000   |  0.137037     |
| 10000  |  0.499688     |
| 20000  |  1.892315     |
| 50000  |  10.29843     |
| 100000 |  1374.101     |
| ...    |  ...          |
+--------+---------------+

    I would suggest you to take a look at Sieve of Eratosthenes. You will find many implementations of it in whichever language you want if you search for this.