Project Euler 10, feedback request

Ok, the below is giving correct output, but, according to tests, it’s too slow.

For now, I don’t have ideas how to optimize it.

function primeSummation(n) {
  
    //generate array of divisors for
    // for future check 'if number is prime'
    
    let upperBound = Math.sqrt(n);
    let oddDivisors = [];
    for (let i = 3; i < upperBound; i += 2) {
  
      let toAddnewDivisor = true;
      for (let divisor of oddDivisors){
        if (i % divisor === 0) {
          toAddnewDivisor = false;
        }
      }
      if (toAddnewDivisor) {
        oddDivisors.push(i);
      }
        
    }
    
    let sumOfPrimes = 0; //result accumulator
    
    //division checks for odd numbers in range below n
    for (let i = 3; i < n; i += 2) {
      let isPrime = true;
      for (let divisor of oddDivisors) {
        if (i % divisor === 0 && i !== divisor) {
          isPrime = false;
          break;
        }
      }
      if (isPrime) {
        sumOfPrimes += i;
      }
    }
    return sumOfPrimes + 2; //add 2 >>> it's the only one even prime
  }
  
  /*test environment: fcc project euler 10
  all test passed except last one:
  for n === 2000000:
  Potential infinite loop detected on line 20. Tests may be failing because of this.
  ---------------------------
  test environment: onecompiler
  
  console.log('expected: 1060, output: ',primeSummation(100));//1060
  console.log('expected: 142913828922, output: ',primeSummation(2000000));//142913828922
  
  */

In the code above I was doing some calculations twice. Fixed that(I think?).
But it is not enough still

function primeSummation(n) {
  
    //generate array of divisors for
    // for future check 'if number is prime'
    
    let upperBound = Math.sqrt(n);
    let oddDivisors = [];
    for (let i = 3; i < upperBound; i += 2) {
  
      let toAddnewDivisor = true;
      for (let divisor of oddDivisors){
        if (i % divisor === 0) {
          toAddnewDivisor = false;
        }
      }
      if (toAddnewDivisor) {
        oddDivisors.push(i);
      }
        
    }
    

    //was unexpected first, but oddDivisors is array of prime numbers
    let sumOfPrimes = oddDivisors.reduce((a, b) => a + b, 0); //result accumulator
    
    //console.log(oddDivisors)//for tests only
    //let primesArray = []// for tests only
    //console.log(oddDivisors[oddDivisors.length - 1])


    //division checks for odd numbers in range below n
    //part of the job was done in the code above
    for (let i = oddDivisors[oddDivisors.length - 1] + 2; i < n; i += 2) {
      let isPrime = true;
      for (let divisor of oddDivisors) {
        if (i % divisor === 0 && i !== divisor) {
          isPrime = false;
          break;
        }
      }
      if (isPrime) {
        sumOfPrimes += i;
        //primesArray.push(i);//for tests only
      }
    }
    //console.log(primesArray);//for tests only
    return sumOfPrimes + 2; //add 2 >>> it's the only one even prime
  }
  
  /*test environment: fcc project euler 10
  all test passed except last one:
  for n === 2000000:
  Potential infinite loop detected on line 20. Tests may be failing because of this.
  ---------------------------
  test environment: onecompiler
  
  console.log('expected: 1060, output: ',primeSummation(100));//1060
  console.log('expected: 142913828922, output: ',primeSummation(2000000));//142913828922
  
  */

This is a classic problem for a prime number sieve, which is the fastest way to find primes.

Ok, I’ve managed to implement this ancient sieve. It was enough to pass the tests, but it was still not really fast.

My original problem was that I didn’t knew word ‘sieve’ in English)

I used object here. But before that I was trying to use one-dimensional arrays… and was stuck with ‘how to use filter, slice, splice etc’ in proper fashion. Need to work on that.

Also while solving this, I implemented function which removes every nth element from array by splicing. For me it looks good and I don’t know if there is a possibility to rewrite it better. It commented out at the top of code.

/* UNIT1 */
/* was not used in the final solution

const removeEveryNthItem = (arr, n) => {
  const maxIndex = Math.floor(arr.length / n);
  copyArr = [...arr];
  for (let i = maxIndex; i >= 0; i--) {
    copyArr.splice((i + 1) * n - 1, 1);
  }
  return copyArr;
}

*/


function primeSummation(n) {
  
  //generating list of numbers:
  let arrayOfNumbers = {};
  for (let i = 2; i < n; i++) {
    arrayOfNumbers[i] = true;
  }
  //console.log(arrayOfNumbers)//tests only
 
 let termCondition = Math.sqrt(n);
 
 for (let i = 2; i < termCondition; i++) {
   if (arrayOfNumbers[i]) {
     let startingJ = Math.pow(i, 2);
     for (let j = startingJ; j < n; j += i) {
       //console.log(j);//tests only
       arrayOfNumbers[j] = false;
     }
   }
 }
 
 let sumOfPrimes = 0;
 
 for (let number in arrayOfNumbers) {
   if (arrayOfNumbers[number]) {
     sumOfPrimes += Number(number);
   }
 }
 
 return sumOfPrimes;
 
}

//fcc tests passed

The splice method is not very efficient. There is a lot going on behind the scenes.

1 Like

On stackoverflow there are also options with filter, like this:

//TASK: remove every third element
var thisArray = ['a', 'b', 'c', 'd', 'e', 'f', 'g'];

thisArray = thisArray.filter(function(value, index) {
  return (index + 1) % 3 != 0;
});


console.log(thisArray);//[ 'a', 'b', 'd', 'e', 'g' ]

But they are all using either % or / operator. For now I can’t figure out how not to use splice and avoid all this division(I was told that division is not very good also).
I guess I will try some slicing…

Just directly index in and flip entries from true to false. No splicing.

But you can really speed up by carefully selecting loop bounds.

1 Like