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

Question

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.

Hmm, I tested it with the number 15 which is an odd, non-prime number, and it came back false, which is correct. So it does seem to be working... — BexLE, Feb 01 '13 at 16:18
and if you were to test it with 3 which is an odd prime number, it would come back false too, which is incorrect. :) — Will Ness, Feb 02 '13 at 14:07

score 31 · Accepted Answer · edited Aug 03 '18 at 12:49

31

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++)

edited Aug 03 '18 at 12:49

Tomer Shemesh

10,278
4
21
44

answered Feb 01 '13 at 16:10

Rohit Jain

209,639
45
409
525

1

Thank you, and everyone else who pointed this out! I can't believe I didn't spot this : ) – BexLE Feb 01 '13 at 16:15

score 31 · Answer 2 · edited Nov 09 '14 at 11:50

31

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;
}

edited Nov 09 '14 at 11:50

ROMANIA_engineer

54,432
29
203
199

answered Feb 01 '13 at 16:18

Peter Lawrey

525,659
79
751
1,130

BTW 2 is a Prime number ;) – Vishal K Feb 01 '13 at 16:34
@VishalK Which is why I have a "fast even test" ;) – Peter Lawrey Feb 01 '13 at 16:36
1

But isn’t `(2 & 1) == 0`? So `isPrime(2) == false`, which is false. – Lumen Feb 01 '13 at 17:16
I forgot that all even numbers except 2 are non prime. – Peter Lawrey Feb 01 '13 at 17:42
Note that a sieve is much faster: http://stackoverflow.com/questions/1042902/most-elegant-way-to-generate-prime-numbers/1043247#1043247 – starblue Feb 03 '13 at 13:31
1

@starblue sieve is much faster if you need a collection of prime numbers. If you want to test just one prime number, this search is much faster. – Peter Lawrey Feb 03 '13 at 17:37
`i*i <= n` may overflow, that's not a good solution. Better calculate `sqrt(n)` before the loop and compare against it. – Archie Feb 08 '13 at 15:53
@Archie That is highly unlikely as `n` would have to be greater than the largest square you can represent with a `long` whereas sqrt(n) equally has round errors for such large `long` values. i.e. it can fail with much smaller numbers. It could be faster for large values. – Peter Lawrey Feb 14 '13 at 18:10
@PeterLawrey Well, it's Java; `long` is 64 bits and `int` is 32 bits. And `sqrt(max_long) > max_int`. – Archie Feb 14 '13 at 22:39
@PeterLawrey I am inline with using sqrt(n) before the loop suggested by Archie, at least this will avoid finding the square on each iteration. sqrt(n) is one time computation for the whole iteration. – Kanagavelu Sugumar Sep 02 '15 at 09:37
@KanagaveluSugumar it is but also it's very expensive. As `i * i` can be done concurrently with `n % i` you would need to do a micro -benchmark to see if it really helped. – Peter Lawrey Sep 02 '15 at 09:52

Zoltán Tamási · Answer 3 · 2017-08-27T11:34:57.407

3

You should write i < n, because the last iteration step will give you true.

edited Aug 27 '17 at 11:34

answered Feb 01 '13 at 16:11

Zoltán Tamási

12,249
8
65
93

score 3 · Answer 4 · answered Feb 01 '13 at 16:12

3

Error is i<=n

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

answered Feb 01 '13 at 16:12

Gabriele Mariotti

320,139
94
887
841

score 2 · Answer 5 · edited Feb 01 '13 at 17:56

public class PrimeNumberCheck {
  private static int maxNumberToCheck = 100;

  public PrimeNumberCheck() {
  }

    public static void main(String[] args) {
      PrimeNumberCheck primeNumberCheck = new PrimeNumberCheck();

      for(int ii=0;ii < maxNumberToCheck; ii++) {
        boolean isPrimeNumber = primeNumberCheck.isPrime(ii);

      System.out.println(ii + " is " + (isPrimeNumber == true ? "prime." : "not prime."));
    }
  }

  private boolean isPrime(int numberToCheck) {    
    boolean isPrime = true;

    if(numberToCheck < 2) {
      isPrime = false;
    }

    for(int ii=2;ii<numberToCheck;ii++) {
      if(numberToCheck%ii == 0) {
        isPrime = false;
        break;
      }
    }

    return isPrime;
  }
}

Kanagavelu Sugumar · Answer 6 · 2015-09-03T20:35:12.607

1

With this code number divisible by 3 will be skipped the for loop code initialization.
For loop iteration will also skip multiples of 3.

private static boolean isPrime(int n) {

    if ((n > 2 && (n & 1) == 0) // check is it even
       || n <= 1  //check for -ve
       || (n > 3 && (n % 3 ==  0))) {  //check for 3 divisiable
            return false;
    }

    int maxLookup = (int) Math.sqrt(n);
    for (int i = 3; (i+2) <= maxLookup; i = i + 6) {
        if (n % (i+2) == 0 || n % (i+4) == 0) {
            return false;
        }
    }
    return true;
}

edited Sep 03 '15 at 20:35

answered Sep 03 '15 at 20:25

Kanagavelu Sugumar

18,766
20
94
101

Why till sqrt? Watch https://www.youtube.com/watch?v=7VPA-HjjUmU&list=PL2_aWCzGMAwLL-mEB4ef20f3iqWMGWa25&index=3 – Kanagavelu Sugumar Sep 03 '15 at 20:48

score 1 · Answer 7 · answered Apr 09 '17 at 04:35

You could also use some simple Math property for this in your for loop.

A number 'n' will be a prime number if and only if it is divisible by itself or 1. If a number is not a prime number it will have two factors:

n = a * b

you can use the for loop to check till sqrt of the number 'n' instead of going all the way to 'n'. As in if 'a' and 'b' both are greater than the sqrt of the number 'n', a*b would be greater than 'n'. So at least one of the factors must be less than or equal to the square root.

so your loop would be something like below:

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

By doing this you would drastically reduce the run time complexity of the code. I think it would come down to O(n/2).

Ram Kumar · Answer 8 · 2017-04-26T06:03:57.300

1

One of the fastest way is looping only till the square root of n.

  private static boolean isPrime(int n){
        int square = (int)Math.ceil((Math.sqrt(n)));//find the square root
        HashSet<Integer> nos = new HashSet<>(); 
        for(int i=1;i<=square;i++){
            if(n%i==0){
                if(n/i==i){
                    nos.add(i);
                }else{
                    nos.add(i);
                    int rem = n/i;
                    nos.add(rem);
                }
            }
        }
        return nos.size()==2;//if contains 1 and n then prime
    }

edited Apr 26 '17 at 06:03

answered Apr 26 '17 at 05:36

Ram Kumar

105
2
13

Hm, maybe it's faster (is it?), but it makes HashSet that might grow quite considerably... – Stefan Reich Sep 06 '17 at 19:09

score 0 · Answer 9 · edited Feb 01 '13 at 16:12

0

You are checking i<=n.So when i==n, you will get 0 only and it will return false always.Try i<=(n/2).No need to check until i<n.

edited Feb 01 '13 at 16:12

PermGenError

45,977
8
87
106

answered Feb 01 '13 at 16:11

Renjith

3,274
19
39

The check will be i less than OR EQUAL TO n. – Renjith Feb 01 '13 at 16:16
The maximum number that can be a factor of n is n/2. – Renjith Feb 01 '13 at 16:17
3

Maximum number that can be factor should be check till `sqrt(n)` not `(n/2)` since if `n/2` will be factor then it means `n = n/2 * 2` , so `2` will also be factor and would be detected earlier. – Pshemo Feb 01 '13 at 16:21

score 0 · Answer 10 · answered Aug 13 '14 at 17:57

The mentioned above algorithm treats 1 as prime though it is not. Hence here is the solution.

static boolean isPrime(int n) {
  int perfect_modulo = 0;
  boolean prime = false;

  for ( int i = 1; i <=  n; i++ ) {
    if ( n % i == 0 ) {
      perfect_modulo += 1;
    }
  }
  if ( perfect_modulo == 2 ) {
    prime = true;
  }

  return prime;
}

score 0 · Answer 11 · answered Apr 23 '18 at 19:47

0

Doing it the Java 8 way is nicer and cleaner

    private static boolean isPrimeA(final int number) {
        return IntStream
               .rangeClosed(2, number/2)
               .noneMatch(i -> number%i == 0);
    }

answered Apr 23 '18 at 19:47

Sal

11
3

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

11 Answers11

Linked

Related