1

I'm running the following code to find the sum of the first 10,000,000 prime numbers. How can I optimize it such that it doesn't take forever to obtain the result(the sum of prime numbers)?

sum=0
num=2
iterator=0

while iterator<10000000:
    prime = True

    for i in range(2,num):
        if (num%i==0):
            prime = False

    if prime:
        sum=sum+num
         # print (num, sum, iterator)
        iterator=iterator+1
    num=num+1

print(sum)
Alex
  • 18,484
  • 8
  • 60
  • 80
lottee
  • 113
  • 1
  • 7
  • use a prime sieve probably – Joran Beasley Mar 01 '18 at 00:30
  • 2
    It's bad practice to name a variable that overrides a builtin function (e.g. `sum`). Furthermore `iterator` has a very specific meaning in Python, so I'd avoid that as a variable name too. – Alex Mar 01 '18 at 00:34
  • 1
    Possible duplicate of [using filter and generator to generator endless prime number in python](https://stackoverflow.com/questions/41668867/using-filter-and-generator-to-generator-endless-prime-number-in-python) – DYZ Mar 01 '18 at 00:38
  • 2
    No need to change anything, it already won't run forever. – Stefan Pochmann Mar 01 '18 at 00:38

3 Answers3

3

the 10,000,000 th prime is approximately n * ln(n) + n * ln( ln(n) ) or ~188980383 ... then you can use a sieve to find all primes under that value (discard any extras ... (ie you will get about 50k extra prime numbers when using 10million, note this took approximately 8 seconds for me))

see also : Finding first n primes?

see also : Fastest way to list all primes below N

Joran Beasley
  • 110,522
  • 12
  • 160
  • 179
1

You can use the Sieve of Eratosthenes. It's a much faster method to find the first n prime numbers.

dshus
  • 170
  • 11
  • isnt that to find all primes under N ... which is significantly different than the nth prime (but you are right in essense) – Joran Beasley Mar 01 '18 at 00:32
  • 1
    @JoranBeasley Yes, that is what the question is asking and what I specified in my answer. This finds the first n primes, which you can use to calculate the sum. – dshus Mar 01 '18 at 00:35
  • no... its asking for the sum of the first 10Million primes... not the sum of all primes under 10million (there are about 650k primes that are less than 10Million) – Joran Beasley Mar 01 '18 at 00:38
  • @JoranBeasley Oh, I see. Okay, my bad. – dshus Mar 01 '18 at 00:39
0

It turns out the Sieve of Eratosthenes is fairly simple to implement in Python by using correct slicing. So you can use it to recover the n first primes and sum them.

It was pointed out in Joran Beasley's answer that an upper bound for the n-th prime is n * ln(n) + n * ln( ln(n) ), which we can use and then discrard the extra primes. Note that this bound does not work for n smaller than 6.

from math import log

def sum_n_primes(n):
    # Calculate the upper bound
    upper = int(n * ( log(n) + log(log(n))))

    # Prepare our Sieve, for readability we make index match the number by adding 0 and 1
    primes = [False] * 2 + [True] * (upper - 1)

    # Remove non-primes
    for x in range(2, int(upper**(1/2) + 1)):
        if primes[x]:
            primes[2*x::x] = [False] * (upper // x - 1) # Replace // by / in Python2

    # Sum the n first primes
    return sum([x for x, is_prime in enumerate(primes) if is_prime][:n])

It takes a few seconds, but outputs that the sum of the 10,000,000 first primes is 870530414842019.

If you need n to be any higher, one solution would be to improve your upper bound.

Olivier Melançon
  • 21,584
  • 4
  • 41
  • 73