Project Euler: #10 - Summation of primes

Problem

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

Find the sum of all the primes below two million.

Problem Description

The problem is pretty self-explanatory!

Sum of primes below 10 is 17.

Find the sum of primes below 2000000.

Approach

To calculate the sum of primes, we can use the brute force algorithm method, which solves a problem through exhaustion - it goes through all possible choices until a solution is found.

The brute force method is simple and consistent but very slow. It affects the time complexity of the program as it depends on the size of the input, in our case we need to loop two million times.

We loop through the numbers till 2 million and push them to an array allPrimes, if it is a prime number.

The steps involved in determining isPrime(n) is the same as we did with problem #3 - Largest Prime factor and problem #7 - 10001st Prime. Except that here, I opted for a while loop instead of for loop.

Finally, using the array reduce() method, the sum of all the primes in the array allPrimes is calculated.

Solution

const isPrime = n => {
    if (n === 2) return true;
    if (n === 3) return true;
    if (n % 2 === 0) return false;
    if (n % 3 === 0) return false;

    let i = 5,
        next = 2;
    while (i * i <= n) {
        if (n % i === 0) {
            return false;
        }
        i += next;
        next = 6 - next;
    }
    return true;
}

let allPrimes = [];

for (let i = 2; i <= 2000000; i++) {
    if (isPrime(i)) allPrimes.push(i);
}

console.log(allPrimes.reduce((a, b) => a + b, 0));

You can find my solution on GitHub 10.

The above solution failed 3 out of 10 test cases in Hacker rank(Of course Hacker rank uses a variety of test cases from a small number to a very big number).

Hence I tweaked the solution to achieve the time complexity for passing all the test cases.

First, I adjusted a bit while calculating isPrime(n).

const isPrime = n => {
            if (n === 1) return false;

            if (n < 4) return true; // 2 & 3 are prime
            if (n % 2 === 0) return false;

            // We have excluded 4, 6 & 8 in the previous step.
            if (n < 9) return true; 
            if (n % 3 === 0) return false;

            let i = 5;

            // n rounded to the greatest integer s so that s*s <= n
            let s = Math.floor(Math.sqrt(n)); 
            while (i <= s) {
                if (n % i === 0) return false;
                if (n % (i + 2) === 0) return false;
                i = i + 6;
            }

            return true;
        }

Note: The below code is only for the Hacker Rank solution to pass all test cases. 👇

Even after this, 2 test cases were timed out. So instead of getting the allPrimes for every test case, declare the allPrimes array as global to all test cases, push the prime numbers into this array from where we left in the last test case till we reach the current n. In this way, we won't repeat the same process again and again for each test case.

function main() {
    var t = parseInt(readLine());

    let allPrimes = []; // Moved this here. Common to all the input.

    for(var a0 = 0; a0 < t; a0++){
        var n = parseInt(readLine());

        // let allPrimes = [];
        let sum = 0, 
            temp = true;
        // If allPrimes has items, get the last item to lastNum
        // Else initialise lastNum to 1.
        // We will loop through from lastNum till we reach n
        // and add the prime numbers into the array allPrimes
        let lastNum = allPrimes.length !== 0 ? 
                            allPrimes[allPrimes.length-1] : 1;
        // If lastNum is greater than n, then we already have 
        // the prime numbers till n in the allPrime array.
        // So loop through allPrime array till <= n, and 
        // sum all the prime numbers
        if(lastNum > n){
            temp = false;
            for(let l = 0 ; l < allPrimes.length ; l++ ){
                if(allPrimes[l] <= n){
                    sum += allPrimes[l];  
                }
            }
        }
        // Else, from lastNum + 1, we need to find the prime till n
        lastNum++
        while(lastNum <= n){
            if(isPrime(lastNum)){
                allPrimes.push(lastNum)
            }
            lastNum++
        }
        if(temp){
            sum = allPrimes.reduce((acc,cur) => acc + cur, 0)
        }
        console.log(sum)
    }

}

If you have another or a better solution, please leave it in the comments below.

For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.

Thank you!

Project Euler: #10 - Summation of primes

Comments

Project Euler: JS Solution Explained!

Project Euler: #11 - Largest product in a grid

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #11 - Largest product in a grid

More from this blog

Problem

Problem Description

Approach

Solution