# 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**

```javascript
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](https://github.com/sansk/project-euler-solutions-javascript/tree/main/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)`.

```javascript
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.

```javascript
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.**](https://theintrovertcoder.hashnode.dev/series/project-euler)

Thank you!