A faster solution for Project Euler question 10

Question

I have solved the question 10 regarding sum of all primes under 2 million, however my code takes over a few minutes to calculate the result.

I was just wondering if there is any way to optimise it to make it run faster ?

• The code takes an upper limit
• Generates an array
• Iterates through it and removes multiples of a number, replacing it with 0
• Takes that filtered array and loops through the next non zero number
• Increases this number till it is sqrt of the limit.
• Prints out what is left.

import numpy as np


def sievePrime(n):
    array = np.arange(2, n)

    tempSieve = [2]

    for value in range(2, int(np.floor(np.sqrt(n)))):
        if tempSieve[value - 2] != value:
            continue
        else:
            for x in range(len(array)):
                if array[x] % value == 0 and array[x] != value:
                    array[x] = 0
                    tempSieve = array

    return sum(array)


print(sievePrime(2000000))

Thank you for your time.

Answer 1

Thanks for the input. I was able to improve the code by changing how a number is checked for prime.

The code finishes under 2 seconds instead of minutes.

Instead of counting from beginning to end for array, it counts from the prime number to the end of the array with increments of the prime number.

Thanks again for the suggestions.

import numpy as np
import time

start_time = time.time()


def sievePrime(n):
    array = np.arange(2, n)

    tempsieve = [2]

    for value in range(2, int(np.floor(np.sqrt(n)))):
        if tempsieve[value - 2] != value:
            continue
        else:
            for x in range(value, len(range(n)), value):
                if array[x - 2] % value == 0 and array[x - 2] != value:
                    array[x - 2] = 0
                    tempsieve = array
                else:
                    continue

    return sum(array)


print(sievePrime(2000000))
print("--- %s seconds ---" % (time.time() - start_time))