Question about Prime number exercise

JavaScript
1

In the Javascript part 1 course, the last exercise of control flow is show all the prime numbers within the limit.

The script is:

function showPrimes(limit){
for (let number=2; number <= limit; number++{
let isPrime = true;
for (let factor = 2; factor < number; factor++){
if (number % factor === 0){
isPrime = false;
break;
}
}
if (isPrime) console.log(number);
}
}

What I can’t figure out is this part:
if (number % factor === 0)

I’m thinking that factor = 2, and 2 < 3, so factor +1. Iterate it, now all the factors are 2-10.

The next is after number/factor, if there is no remainder, it is not a prime number.
So 3(number)/2(factor), there is a remainder so 3 is a prime number.
The next is what confuse me.
Both number and factor increment by 1, so now 4/3, this also has a remainder, so according to the code, 4 is also a prime number.

What am I thinking wrongly here?

1 Like
2

According to the code, 4 is not a prime number. You can run the code to confirm.

When number is 4 and factor is 2, then number % factor === 0 and isPrime is set to false and we break out of the inner loop and move on to the next number.

number and factor are not incremented at the same time. Maybe some extra logging will help?

function showPrimes(limit) {
  for (let number=2; number <= limit; number++) {
    console.log("number is " + number);
    let isPrime = true;
    for (let factor = 2; factor < number; factor++) {
      console.log("factor is " + factor);
      if (number % factor === 0) {
        isPrime = false;
        console.log("not a prime");
        break;
      }
    }
    if (isPrime) {
      console.log(number);
    }
  }
}
1 Like
3

I think the part that is confusing you is that the inner loop runs to completion before the outer loop increments.

For example, if I have the following code:

for (let i = 0; i < 3; i++) {
  for (let j = 0; j < 3; j++) {
    console.log("i =", i, ", j =", j);
  }
}

It will print:

i = 0, j = 0
i = 0, j = 1
i = 0, j = 2
i = 1, j = 0
i = 1, j = 1
i = 1, j = 2
i = 2, j = 0
i = 2, j = 1
i = 2, j = 2

See how the outer for loop only increments after the inner for loop has completed. If we use a method for the inner for loop, the logic becomes even clearer:

function showPrimes(limit) {
  for (let number = 2; number <= limit; number++) {
    if (isPrime(number)) console.log(number);
  }
}

function isPrime(number) {
  for (let factor = 2; factor < number; factor++) {
    if (number % factor === 0) return false;
  }
  return true;
}

Aside: this is one of the reasons breaking things down into functions can greatly improve the readability of your code.

So, even though each for loop increments by 1, they are doing so at different times. Extracting a function here helps with the readability.

Lastly, this is probably the least efficient way to determine the primes up to a given number and would be something I would call a “brute force” method. If you ever need to do this in an interview, please use the Sieve of Eratosthenes.

3 Likes
4

Hi eelsholz, thanks for the explanation! This is very helpful!
Now I know that the outer loop and inner loop does increment at the same time.

5

Hi jmrunkle, your explanation is awesome!
Also thanks for the additional info about Sieve of Eratosthenes.
I will read about it.

6

I´ve got a question too, in the first iteration of both for loops, when number = 2 in the outer for loop, and factor < number (which means less than 2) in the inner for loop, what would be the value of the factor then? so then within the if condition, the division doesn’t have a remainder = 0

7

When the outer loop variable number is 2, the inner loop is never really entered because the initialization sets the factor to 2 and then the condition is checked before the body executes. Since the condition is factor < number and 2<2 returns false we never execute the body of the for loop. Therefore we skip over that and return true. It is easier to reason about if you use my factored version where we have a helper method called isPrime.

2 Likes
8

A little over a year later and wow this helped me understand it so clearly. Thanks very much! Wasn’t truly grasping the inner loop until adding the console log.

1 Like