CODEWITHSUNDEEP
javaalgorithm
Trideep
Trideep

Reputation: 51

Why does the code not work in this instance?

I am struggling to understand why code wouldn't work. According to the truth table/logic gates for AND and OR https://en.wikipedia.org/wiki/Truth_table I would assume that I would be able to have an if statement inside the for-loop such that (p < 2 || p % i == 0) would work for finding prime numbers but it fails when considering negative numbers.

I know that if you if take out the p < 2 and write it as an if statement outside this for-loop it works, but if the p < 2 is inside the for-loop it does not work. Why is this so?

public class test {
    public static void main(String [] args) {
        System.out.println("Hello World!");

        int a = 7;
        System.out.println("A is Prime: " + isPrime(a));
        System.out.println();

        int b = 4;
        System.out.println("B is Prime: " + isPrime(b));
        System.out.println();

        int c = -7;
        System.out.println("C is Prime: " + isPrime(c));
        System.out.println();

        int d = 53;
        System.out.println("D is Prime: " + isPrime(d));
    }

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

Upvotes: 0

Views: 83

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114300

You may want to invest in Math.abs(int):

public static boolean isPrime(int p) {
    p = Math.abs(p);
    for (int i = 2; i < p; i++) {
        ...

This will ensure that p is always non-negative, and your initial assumptions about how the loop should behave are justified.

Upvotes: 1

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476594

Because for p < 2, the body of the for loop is never performed. Indeed:

for (int i = 2; i < p; i++) {
    // ...
}

If p = 2, then it initializes i = 2, and then checks i < p which fails, and hence the body is never executed. It skips the for loop, and thus returns true.

We can fix it by performing a check before (or after) the for loop, and even boost the performance of the loop slighly:

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

We can simply return false first for all values less than 2, and true for 2. Furthermore we only need to iterate up to √p, since if there is a value j larger than √p that divides p, then there is a smaller value i = p/j that is smaller than √p that will already be checked. We furthermore only need to check odd numbers, since even numbers are already implied by the division by 2.

Upvotes: 6

Related Questions