Summation of Primes

Download Video

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all the primes below n.

Slow Solution (uses less memory)

let primeSummation = (n) => {

    let sum = 0
    let candidateValue = 0

		/* Add first prime number (2) to sum */
    if(n > 2){
        sum = sum + 2
        console.log('Added prime ' + 2 + ', sum is now ' + sum)
        candidateValue = 3
    }

		/* While we haven't crossed rthe limit*/
    while(candidateValue < n){
		
				/* Assume candidate value is prime */
        let isPrime = true

				/* Try dividing candidate value by all odd numbers between
					3 and itself */
        let divisor
        for(divisor = 3; divisor < candidateValue; divisor ++){
						/* If divided without remainder, its not prime */
            if(candidateValue % divisor === 0){
                isPrime = false
            }
        }

				/* If still prime, add it to sum */
        if(isPrime){
            sum = sum + candidateValue
            console.log('Added prime ' + candidateValue + ', sum is now ' + sum)
        }

				/* Try with next odd number */
        candidateValue = candidateValue + 2        
    }

    return sum
}

For 2 million, this took about 1 hour 15 mins to complete :

slow-solution

So, we ideally need a faster solution.

Faster Solution (uses more memory)

/* Solution Function */
let primeSummation = (n) => {

    let sum = 0

    /* Array of prime values to sum. Index is the same as value */
    let arrayToSum = [0, 0]
    let i
    /* Assume that all values from 2 are prime */
    for(i = 2; i < n; i ++){
        arrayToSum.push(i)
    }

    /* Go through each index between 2 and n */
    for(i = 2; i < n; i ++){

        /* If the number hasn't already been removed (set to 0) */
        if(arrayToSum[i] !== 0){
            let j
            /* Go through array and remove all its multiples (set to 0) */
            for(j = 2*i; j < n; j += i){
                if(arrayToSum[j] % i === 0){
                    arrayToSum[j] = 0
                }
            }
        }
    }

    /* Add remaining values from array */
    for(i = 0; i < arrayToSum.length; i ++){
        if(arrayToSum[i] != 0){
            console.log('Added prime ' + arrayToSum[i] + ', sum is now ' + sum)
        }
        sum = sum + arrayToSum[i]
    }

    return sum

}

/* Check Solution */
console.log('Result is ' + primeSummation(2000000))

The Sieve of Eratosthenes

Ganesh H