summation of all prime numbers under 2 million

Question

this code put calculate all the prime numbers that is bellow 2 million and the calculate a summation of them, I don't think that the prime numbers are wrong but I receive sum of them as 143010484903 , but the correct answer is 142913828922.

can anyone help me what's wrong? I'm new to JS.

let num = 3;
let primes = [2];

while (num < 2000000) {
  let sqrtNum = Math.floor(Math.sqrt(num));
  for (i = 0; sqrtNum >= primes[i]; i++) {
    if (num % primes[i] == 0) {
      num += 2;
      i = 0;
    } else {
      continue;
    }
  }
  primes.push(num);
  num += 2;
}

let sum = 0;
for (let i = 0; primes[i] < 2000000; i++) {
  sum += primes[i];
}

console.log(sum);

Answer 1

Your algorithm is adding composites to your primes list:

let num = 3;
let primes = [2];

while (num < 123) {
  let sqrtNum = Math.floor(Math.sqrt(num));
  for (i = 0; sqrtNum >= primes[i]; i++) {
    if (num % primes[i] == 0) {
      num += 2;
      i = 0;
    } else {
      continue;
    }
  }
  primes.push(num);
  num += 2;
}
console.log(...primes)

Notice 121 (11 x 11) in the above list.

The problem is in the logic of your while loop and the way you are managing the variable num. Consider what happens when you are testing the composite value 115 You'll be in the portion of your loop where n = 115:

  let sqrtNum = Math.floor(Math.sqrt(num));  // sqrtNum == 10
  for (i = 0; sqrtNum >= primes[i]; i++) {   // testing against [2, 3, 5, 7, 9]
    if (num % primes[i] == 0) {              // on the 3rd loop you find 115
      num += 2;                              // is divisible by 5 and increase
      i = 0;                                 // nums to 117,and find it's composite
                                             // eventually nums is 121 but you haven't changed
    } else {                                 // sqrtNum to refect you now need to search
      continue;                              // up to 11 so you think 121 is prime
    }
  }
  primes.push(num);
  num += 2;
}

This doesn't happen often, which is why your sum is close. Changing to math.ceil appears to fix this because ceil(Math.sqrt(115)) is 11, but I'm not sure how you can prove this will always be correct.

A better idea is the sieve posted in a different answer. But here's a fix that sticks close to your code but manages num so you don't increase num without recalculating sqrtNum:

let num = 3;
let primes =[2];

while(num <= 130) {
  let composite = false
  let sqrtNum = Math.floor(Math.sqrt(num)); // sqrtNum will be calculated for each change of num
  for(i = 0; sqrtNum >= primes[i]; i++) {
    if(num % primes[i] == 0) {
      composite = true
      break
    } 
  }
  if (!composite){
    primes.push(num);
  }
  num += 2
}
// no 121!
console.log(...primes);

Answer 2

I think you do have some extra primes which are greater than 2000000 because you're flooring the value after calculating the square root. Try using .ceil() instead. You can test with even small values try taking 10 and console.log(primes); you can see there is extra value 11 example [2, 3, 5, 7, 11];

let sqrtNum = Math.ceil(Math.sqrt(num));

Answer 3

I'm not entirely sure what the eror is in your code, but somewhere in your inner loop, you mess up. Your primes.length is also longer then in my code.

let primes = [2];

mainLoop: for (let num = 3; num < 2000000; num += 2) {
  let sqrtNum = Math.floor(Math.sqrt(num));
  for (let i = 0; primes[i] <= sqrtNum; i++) {
    if (num % primes[i] == 0) {
      continue mainLoop;
    }
  }
  primes.push(num);
}

let sum = 0;
for (let i = 0; primes[i] < 2000000; i++) {
  sum += primes[i];
}

console.log(sum);

and a quick version with a sieve

var sieve = Array(2000000).fill(false);
var primes = [2];

for(let i=0; i<sieve.length; i+=2) sieve[i] = true;

for(var i=3; i < sieve.length; i+=2){
  if(sieve[i]) continue;
  primes.push(i);
  for(let j=i*i; j<sieve.length; j+=i+i){
    sieve[j] = true;
  }
}

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