Very simple prime number test - I think I'm not understanding the for loop

java loops for-loop iterator primes
BexLE picture BexLE · Feb 1, 2013 · Viewed 80.9k times · Source

I am practicing past exam papers for a basic java exam, and I am finding it difficult to make a for loop work for testing whether a number is prime. I don't want to complicate it by adding efficiency measures for larger numbers, just something that would at least work for 2 digit numbers.

At the moment it always returns false even if n IS a prime number.

I think my problem is that I am getting something wrong with the for loop itself and where to put the "return true;" and "return false;"... I'm sure it's a really basic mistake I'm making...

public boolean isPrime(int n) {
    int i;
    for (i = 2; i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

The reason I couldn't find help elsewhere on stackoverflow is because similar questions were asking for a more complicated implementation to have a more efficient way of doing it.

Answer

Rohit Jain picture Rohit Jain · Feb 1, 2013

Your for loop has a little problem. It should be: -

for (i = 2; i < n; i++)  // replace `i <= n` with `i < n`

Of course you don't want to check the remainder when n is divided by n. It will always give you 1.

In fact, you can even reduce the number of iterations by changing the condition to: - i <= n / 2. Since n can't be divided by a number greater than n / 2, except when we consider n, which we don't have to consider at all.

So, you can change your for loop to: -

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

Related questions

A 'for' loop to iterate over an enum in Java

I have an enum in Java for the cardinal & intermediate directions: public enum Direction { NORTH, NORTHEAST, EAST, SOUTHEAST, SOUTH, SOUTHWEST, WEST, NORTHWEST } How can I write a for loop that iterates through each of these enum values?

Read More
Breaking out of a for loop in Java

In my code I have a for loop that iterates through a method of code until it meets the for condition. Is there anyway to break out of this for loop? So if we look at the code below, what …

Read More
How to make for loops in Java increase by increments other than 1

If you have a for loop like this: for(j = 0; j<=90; j++){} It works fine. But when you have a for loop like this: for(j = 0; j<=90; j+3){} it doesn't work. Could someone please explain this to me?

Read More