Sieve of Eratosthenes

Why is statement 2 in this for loop the square root of num? if I input 100, I am looking for an array containing a length of 98 items. It seems to me that statement 2 in the loop would make that array 8 items. That is now how the code works, but I am not understanding the why of it.


function sumPrimes(num) {
  // Prime number sieve
  let isPrime = Array(num + 1).fill(true);
  // 0 and 1 are not prime
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (isPrime[i]) {
      // i has not been marked false -- it is prime
      for (let j = i * i; j <= num; j += i)
        isPrime[j] = false;
    }
  }

  // Sum all values still marked prime
  return isPrime.reduce(
    (sum, prime, index) => prime ? sum + index : sum, 0
  );
}

What is the biggest number that divides into 49? Or 121?

My question is going somewhere, I promise.

Let’s see for 100:

For an integer multiplication, you need 2 factors - a and b.

Because you don’t use 0 and 1 in primes, 2 is the smallest one.
This leads to the conclusion that all multiplications with a greater than 50 don’t have a matching b: 100 / 50 = 2. For a = 51 the b would be smaller than 2.

But because you are searching in ascending order, you actually can stop searching after a is 10, because when you would use 11, the matching b would be smaller than a and you would already have found it, because of the ascending order.

This is why you should think about @JeremyLT’s post.

1 Like

49 is 7 and 121 is 11… so if the number is 100 then i never goes past 10, meaning j never goes past 100, meaning that the function will check every number it needs to if you set it up this way. Is that correct?

Yup. By the time we’ve checked up to the square root, we’ve checked everything we need to.