Sum All Primes - Help Needed with Checking if a Number is Prime

JavaScript
1

I tried writing a function isDivisible that returns false if the number passed to it is divisible, determined by whether or not it can be divided evenly by a number from 2 to the its own square root. I tried to use that mark numbers as prime or not prime. But it seems I wrote it wrong as it marks all numbers aside from 6 as composite.

Without just giving me the solution, please help me with implementing the Sieve of Eratosthenes here. Using a working isDivisible function. Thanks.

My code so far


function sumPrimes(num) {
const isDivisible = value => {
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (value % i !== 0) {
      return false;
    }
  }
  return true;
}

const primes = [];
for (let i = 2; i <= num; i++) {
  if (isDivisible(i)) {
    continue;
  } else {
    primes.push(i);
  }
}

console.log(primes)
}

sumPrimes(10);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/84.0.4147.89 Safari/537.36 Edg/84.0.522.40.

Challenge: Sum All Primes

Link to the challenge:

2

I think your issue is here. Your function is called isDivisible, but I think it should be called isPrime because it returns true if the number is prime. You should then track the number as prime if isPrime returns true.

The big picture for the Sieve of Eratosthenes is that you make a big boolean array for all numbers from 1 to num. You ‘guess’ all values are prime, or true. You then start at 2 and mark all multiples of 2 as not prime, or false. Keep working through the array, marking all multiples of any numbers marked as prime as not prime values.

3

My function actually gives me an array with only 6 in it I push when it returns true, and all numbers from 1 through 10 (when the argument passed in is 10) except 6. So there’s something very wrong with it. Please help me there first.

4

Did you try swapping continue and push like I was talking about above?

Also, the bound for the loop checking for primality should go to sqrt(value). sqrt(num) is too big.

5

You shouldn’t make an array unless you are going to use the array. I bring this up because you can improve the primality check function by dividing by all numbers in your primes array (ideally less than sqrt(val)), or you can sum the primes as you go (which is an idea you want for the fastest Sieve implementation).

6

If I switch continue with push and iterate in that function up to Math.sqrt(value), I get an array of 1, 2, 3, 4, 6, 8 in primes. And continue and push where they would be without switching, I get 5, 7, 9, 10.

7

You can’t have 1 in your array with that change unless you changed something else as well. What is your current code?

8

With this:

function sumPrimes(num) {
  const isPrime = value => {
    for (let i = 2; i <= Math.sqrt(value); i++) {
      if (value % i !== 0) {
        return false;
      }
    }
    return true;
  }

  const primes = [2];
  for (let i = 3; i <= num; i++) {
    if (isPrime(i)) {
      primes.push(i);
    } else {
      continue;
    }
  }

  console.log(primes)
}

I get [ 2, 3, 4, 6, 8 ] in the console.

9

I just changed it to this:

function sumPrimes(num) {
  const isPrime = value => {
    for (let i = 2; i <= Math.sqrt(value); i++) {
      if (value % i !== 0) {
        return false;
      }
    }
    return true;
  }

  let primes = [];
  for (let i = 2; i <= num; i++) {
    primes.push(i);
  }

  primes = primes.filter(value => isPrime(value))

  console.log(primes)
}

Of course, it still gives me [ 2, 3, 4, 6, 8 ] in the console when I do console.log(primes).

What am I doing wrong here?

10

It might be the fancy syntax for declaring the function that’s causing an issue with isPrime? It looks like ok logic

11

Because of what you said about the fastest way to implement the Sieve, I tried this:

function sumPrimes(num) {
  let primes = [2];
  for (let i = 3; i <= num; i++) {
    if (i % primes[i] !== 0) {
      primes.push(i);
    }
  }

  console.log(primes)
}

I get this array logged to the console:
[ 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

Do I at least have the right idea there?

As for the syntax for defining the function: that doesn’t seem to be the problem because the problem persists when I define the function like

const isPrime = function(value) {
   // ...
}

as well. And I had my doubts about that making a difference before I checked, too.

12

Ah, I see it. The prime checking logic only works correctly when you assume that the number is prime and check for divisors. That means you need to return false when a number evenly divides the value.(=== vs !==)

Originally, you were assuming the value is not prime and returning that the value was in fact prime if there was a number that was not a divisor of the value. That won’t work. You need to assume that the value is prime and return false if you find a divisor of the value.

13 
function sumPrimes(num) {
  const isPrime = value => {
    for (let i = 2, s = Math.sqrt(value); i <= s; i++) {
      if (value % i === 0) {
        return false;
      }
    }
    return num > 1;
  }

  let primes = [];
  for (let i = 2; i <= num; i++) {
    primes.push(i);
  }

  primes = primes.filter(value => isPrime(value));
  
  return primes.reduce((result, prime) => result + prime);
}

I had to look at a stackOverflow post for a function to check if a number is prime, but I finally got it. This works.