Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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.

like image 694
BexLE Avatar asked Feb 01 '13 16:02

BexLE


People also ask

How do you check whether a number is prime or not using for loop?

Program to Check Prime Number Enter a positive integer: 29 29 is a prime number. In the program, a for loop is iterated from i = 2 to i < n/2 . If n is perfectly divisible by i , n is not a prime number. In this case, flag is set to 1, and the loop is terminated using the break statement.

What is the rule to test for a prime number?

To prove whether a number is a prime number, first try dividing it by 2, and see if you get a whole number. If you do, it can't be a prime number. If you don't get a whole number, next try dividing it by prime numbers: 3, 5, 7, 11 (9 is divisible by 3) and so on, always dividing by a prime number (see table below).

How do you know if a number is simple?

Simple methods. The simplest primality test is trial division: given an input number, n, check whether it is evenly divisible by any prime number between 2 and √n (i.e. that the division leaves no remainder). If so, then n is composite. Otherwise, it is prime.

Why prime number we can only loop until square root?

Show activity on this post. To test whether a number is prime or not, why do we have to test whether it is divisible only up to the square root of that number? because if n = a*b and a <= b then a*a <= a*b = n . To clarify, this means we have to test only till floor(sqrt(n)) .


2 Answers

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++)  
like image 143
Rohit Jain Avatar answered Oct 02 '22 20:10

Rohit Jain


You can stop much earlier and skip through the loop faster with:

public boolean isPrime(long n) {
    // fast even test.
    if(n > 2 && (n & 1) == 0)
       return false;
    // only odd factors need to be tested up to n^0.5
    for(int i = 3; i * i <= n; i += 2)
        if (n % i == 0) 
            return false;
    return true;
}
like image 42
Peter Lawrey Avatar answered Oct 02 '22 21:10

Peter Lawrey