How does this program for finding prime numbers work?

Question

I had to write a simple program to print the prime numbers from 2 until 100.

First I did some research about what a prime number is. I tried for a long time, and finally i looked up the answer in the book, sinceIi did not succeed every time writing a 100 % working code.

I understand the answer code for the most part, but one part I don't understand. Let me try to explain. First here is the code from the book:

// Find prime numbers between 2 and 100.
class Prime {

    public static void main(String args[]) {
        int i, j;
        boolean isprime;
        for(i=2; i < 100; i++) {
            isprime = true;
            // see if the number is evenly divisible
            for(j=2; j < i/j; j++)
               // if it is, then it's not prime
               if((i%j) == 0) isprime = false;
            if(isprime)
               System.out.println(i + " is prime.");
        }
    }
}

Ok, so I know this: a prime number can only be divided by itself and by 1.

Let me take number 4 first, this is not a prime, since it can also be divided by 2. So in the code I am following the for loops, but I am stuck at the 'see if the number is evenly divisible' part. In the case of 4, then 4%4 has no remainder, so it is false because of the ==0 part.

So isprime is then false. However, I am reading it wrong or thinking wrong, because if a take a prime number, like 5, i get the same: 5%5 has no remainder, because 5/5 == 1. So in this case 5%5 is also equal to 0, so the isprime should also be false, but the number 5 is a prime number in this case.

So I don't really understand how this check works in the code.

In the begining i is 2 and j is 2, so you get 2%2, also no remainder, but 2 is also a prime number, so I know I am seeing it wrong somewhere.

If someone can explain how this works exactly, I was searching for an hour on the web but could not find it.

Answer 1

First, it should be said - and already mentioned in other answers - that the code you got from the book is wrong (or maybe you missed out copying it). The condition of the internal loop is supposed to be

for(j=2; j <= i/j; j++)

one important lesson from this is that you have to try running even book examples, to see if they work. If you ran this, you would have seen that it marks 4,9,25,49 as prime, when they are not.

But your reading of the code was also not correct. You said that 4 is judged to be not prime because 4%4 == 0. But in fact, a prime number is allowed to be divisible by itself (any number is). So indeed, testing for a prime number by dividing it by itself would not work.

Let's see what this is all about. You understand the outer loop - it is giving you the candidates to test whether they are prime or not.

Then it works like this: assume the current candidate is prime. Try to divide it by all possible divisors. If any of the divisors divides it evenly, mark it as "not prime".

If, after all the possible divisors were tested, none of them got to the point that marks it as "not prime", then it is indeed prime and you can print it.

So the i loop represents the candidates, and the j loop represents the potential divisors. Take the number 15 as an example of i.

• Start j with 2. i/j is 15/2 which is 7. 2 < 7, so we go inside the loop.
  • Is 2 a divisor of 15? No, it isn't. Nothing is done.
• j is now 3. i/j is 15/3 which is 5. 3 < 5, so we continue.
  • Is 3 a divisor of 15? Yes! So set isprime=false.
• j is now 4. i/j is 15/4 which is 3. 4 < 3 is false, so we stop.

As you can see, the step with j=3 above set isprime as false, so we do not print it - it is not prime.

Now let's take a real prime number, like 13:

• Start j with 2. i/j is 13/2 which is 6. 2 < 6, so we go inside the loop.
  • Is 2 a divisor of 13? No, it isn't. Nothing is done.
• j is now 3. i/j is 13/3 which is 4. 3 < 4, so we continue.
  • Is 3 a divisor of 13? No, it isn't. Nothing is done.
• j is now 4. i/j is 13/4 which is 3. 4 < 3 is false, so we stop.

None of the steps set isprime to false. It is still true, so the number 13 is prime and we print it.

Now, the trick here is which candidates we offer for j. Naively, a person writing this the first time would think that the candidates should be all the numbers between 1 and i, excluding 1 and i themselves. So they would write a loop like:

for ( j = 2; j < i; j++ )

But this is wasteful. Why? Suppose you checked the number 15. You found that 3 is a divisor for it. How is that? Because 15 = 3 x 5. But this means that 5 is also a divisor. You don't need to test the divisor which, if you divide by it, you get a divisor that you already tested. So no need to test 5, because we have already tested 3.

So, again, naive programmers might decide that we can just test half the candidates:

for ( j = 2; j <= i / 2; j++ )

But in fact, mathematically speaking, this is still wasteful. Really, we should go only up to the square root of i. Why? Because if a divisor j is bigger than the square root of i, such that j x k = i, then k will be smaller than the square root of i. If k was bigger, then j x k would be bigger than sqrt(i) x sqrt(i) which means they j x k > i. But we know that they are equal to i!

This means that if there is a potential divisor greater than the square root of i, we already found the other divisor, smaller than the square root of i, and tested it and marked i as "not prime".

So this is what your candidate loop is testing. It's basically a simple way of writing

for ( j = 2; j <= Math.sqrt(i); j++ )

Without calling the Math class and without converting the integers to doubles.

But as I said from the start, it's important that the condition is <= rather than <. For numbers which are squares of primes, (4 = 2 x 2, 9 = 3 x 3), the only proper divisor is the number that is equal to their square root.

---

One last note: this book example is still wasteful, because it doesn't stop checking after it found one divisor that makes the number not prime. Finding one divisor is enough. One way to do this is to change the loop condition like this:

for ( j = 2; isprime && j <= i/j; j++ )

So the loop will only continue as long as we still have reason to believe that the number is prime. After a j that marks isprime as false, the loop will automatically stop.

(And of course, this algorithm is not the best algorithm. There are better algorithms. It's just the one everybody starts with).

---

Answers to questions raised in the comments:

An inner loop is always executed afresh. Think of it like this:

If a loop says:

for ( int i = 0; i < 3; i++ ) {
     doSomething();
}

It's equivalent to

doSomething();
doSomething();
doSomething();

So if the "do something" part is in itself a loop:

for ( int i = 0; i < 3; i++ ) {
    for ( int j = 0; j < 2; j++ ) {
        runSomething();
    }
}

is equivalent to:

for ( int j = 0; j < 2; j++ ) {
    runSomething();
}
for ( int j = 0; j < 2; j++ ) {
    runSomething();
}
for ( int j = 0; j < 2; j++ ) {
    runSomething();
}

So you see, each time it's a new j that starts from zero.

As for the question about the curly braces: officially, the format of a for statement is:

for ( initialization; termination; increment )
    statement

The statement can be a single statement, like a method call, an inner for loop, an if statement, or something. In that case, it doesn't need braces. Or the statement can be a block, which is a pair of braces that contains zero or more statements. You are used to seeing a block, and indeed it's recommended to always use a block, not a single statement, as it is easier to add statements.

Answer 2

You have a small error in your inner loop header.

// ...
for(j=2; j <= i/j; j++)
// ...

So instead of < you have to use <= .

Answer 3

The Best way to try to understand this, it's putting System.out.println inside the loop with the values of i, j.

I do it for you with, 2, 3,4, and 5. (only 4 is not prime).

with i = 2 -> condition of the loop is 2 < 2/2 is false, you don't go inside the loop, it's prime.

with i = 3 -> condition of the loop is 2 < 3/2 is false, you don't go inside the loop, it's prime.

with i = 4 -> condition of the loop is 2 < 4/2 is false, you don't go inside the loop and it's prime. maybe the loop condition should be <=

with i = 5 -> condition of the loop is 2 < 5/2 is true, you go inside the loop, and the if condition is false, you add 1 to j and do the loop: 3 < 5/3 is false, you don't go inside the loop, it's prime.

Answer 4

Your problem is in the second for loop

for(j=2; j < i/j; j++)

For 4 and below, the control never enters the inner for loop and you have assumed your number to be prime before you begin checking it, so if the control never enters the loop, it is treated to be prime.

The condition should have been:

for(j=2; j <= i/j; j++)

this will give you the correct result.

Answer 5

I just got done working out the same problem. while it ended up taking a few hours, I forced myself not to look for an answer anywhere but the material preceding the question. I still have no idea what the solution says in the book. My point is try to fight through the aggravation, review the material at hand and you'll get it. Here's my code, ugly but affective.

class primeNum {

public static void main(String args[]){

    int x = 2;
    int y = 2;
    int count;
    System.out.println("The prime numbers between 2 and 100 are: ");

    while (x < 100) {
        count = 0;
        y = 2;

        while (y <= x) {

            if (x % y == 0)  {
                count ++;
            }
        ++y;
        }   
                if (count == 1 ) {
                    System.out.println(" " + x);
            }

        ++x;
    }
}

}