1

Can someone please help clarify to me what is happening when an integer is passed through this method as I am struggling to understand. Thanks!

    public static boolean isPrime(int n) {
            if (n == 1) {
                return false;
            }
    
            for (int i=2; i<= n/2; i++) {
                if (n % i == 0) {
                    return false;
                }
            }
   
            return true;
        }
    }
0xh3xa
  • 4,801
  • 2
  • 14
  • 28
Parker Thompson
  • 11
  • 1
  • 3
    Give it a try with a concrete number like `5` and just go line by line, statement by statement through the code and understand each step. – akuzminykh Jul 10 '20 at 16:42
  • 1
    Unfortunately, this algorithm is flawed. `n/2` should really be `Math.sqrt(n)+1` But the rest is a reasonable attempt. You also need to know what `%` does. – WJS Jul 10 '20 at 16:58
  • 1
    @WSJ it returns true for `n == 0` which is incorrect too – Nowhere Man Jul 10 '20 at 16:59
  • @ParkerThompson check out [this](https://stackoverflow.com/a/62564824/1552534) to see a slightly better implementation. – WJS Jul 10 '20 at 17:04
  • A prime number is any (positive?) integer which is divisible by no other than itself and 1. – nylanderDev Jul 10 '20 at 17:24

1 Answers1

1

When you pass a number to the function, first thing is quick check for the case of 1 which is not prime and can divide all other positive integer without remainder. So, this is specially checked case:

if (n == 1) {
    return false;
}

Then, in for loop you are checking if given number is divisible with any integer up to half of giving number, which allows us to decide whether it is prime or not. If it is divisible, then it is not prime, return false. The way to check if a number is divisible or not is to use mod operator.

But there is a problem; as @WJS said in the comment section, you do not need to check all the number up to n / 2, from Wikipedia:

To test the primality of 100 by trial division, consider all the integer divisors of 100:

2, 4, 5, 10, 20, 25, 50 The largest factor is 100/2 = 50. This is true for all n: all divisors are less than or equal to n/2. Inspecting the divisors, it is determined that some of them are redundant. The list of divisors may be written as:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 which demonstrates the redundancy. Once the divisor 10 is tested, which is √100, the first divisor is simply the dividend of a previous divisor. Therefore, testing divisors greater than √n can be eliminated.

So, your code can be more efficient with following way:

for (int i = 2; i < Math.sqrt(n)+1; i++) {
    if (n % i == 0) {
        return false;
    }
}

Lastly, if you can not divide your number with any number up to its square root, then it means that it is prime, so return true.

Sercan
  • 2,081
  • 2
  • 10
  • 23
  • Thanks so much for your help @Sercan, but what happens if the variable n is equal to a non-prime number that isn't evenly divisible by 2 (ex. 15 or 21)? – Parker Thompson Jul 11 '20 at 18:57
  • For 15 `Math.sqrt(n)+1` = 4.87; your loop will be like `for (int i = 2; i < 4.87; i++)`. It means that there will be iterations for 2, 3 and 4. 2 cannot divide, but 3 divides without remainder, so condition `if (15 % 3 == 0)` is true, therefore method will return false. Same logic for 21. Better try those options in your IDE while debugging to see the behavior. It will be more clear I think. Also please consider upvote and/or accept the answer if it is useful or answers your question :) – Sercan Jul 11 '20 at 19:47