Test a number for primality and return smallest divisor different from 1 if it’s is composite

Question

In this exercise we were asked to test a number for primality and print the results. Additionally – in the case the number is composite – the smallest divisor different from 1 should be printed out. Negative input values shall not pre processed and result in a message.

The second part of that task to improve the performance of the test and wipe out as many redundant and unnecessary comparisons as possible. We were not allowed to use any built-in methods to check for primality.

I have concerns mainly about properly handling input I’m rejecting and naming things (talking about result here).

/**
 * Tests a positive integer for primality.
 * Prints out whether a number is prime, composite or neither.
 */
public class PrimalityTest {
    public static void main(String[] args) {
        // We only test one number, so no other arguments are allowed.
        if (args.length > 1) {
            System.out.println("Too many arguments. Please enter a positive integer prime canidate.");
            System.exit(1);
        }

        int primeCandidate = 0;
        try {
            primeCandidate = Integer.parseInt(args[0]);
        } catch (NumberFormatException e) {
            System.out.println("The entered value was not an integer.");
            System.exit(1);
        }

        if (primeCandidate < 0) {
            System.out.println("Negative numbers are never prime.");
            System.exit(1);
        }

        int result = smallestDivisor(primeCandidate);
        if (result == -1) {
            System.out.println(primeCandidate + " is prime.");
        } else if (result == 1 || result == 0) {
            System.out.println(primeCandidate + " is neither prime nor composite.");
        } else {
            System.out.println(primeCandidate + " is composite and has the smallest divisor " + result + ".");
        }
    }

    /**
     * Returns the smallest divisor of composite numbers or
     * 1 if the number is 1 (not composite, not prime) or
     * -1 if the number is prime (not composite).
     */
    public static int smallestDivisor(int primeCandidate) {
        if (primeCandidate == 0 || primeCandidate == 1) {
            return primeCandidate;
        } else if (primeCandidate <= 3) {
            // 2 and 3 are prime.
            return -1;
        } else if (primeCandidate % 2 == 0) {
            // All numbers greater 2 and divisable by 2 are not prime and the smallest divisor is 2
            return 2;
        } else if (primeCandidate % 3 == 0) {
            // All numbers greater 3 and divisable by 3 are not prime and the smallest divisor is 3
            return 3;
        } else {
            // Checks divisability of numbers in the form of 6k+1 and 6k-1.
            // It starts with: 5 and 7, 11 and 13, 17 and 19, 23 and 25, ...
            for (int i = 5; i * i <= primeCandidate; i += 6) {
                if (primeCandidate % i == 0) {
                    return i;
                } else if (primeCandidate % (i + 2) == 0) {
                    return i + 2;
                }
            }
            // No divisor found, the number is prime.
            return -1;
        }
    }
}

Answer 1

Try to not put logic in the main method. Move all the code in it outside to a parseArguments method, and make main call it. Then try to split parseArguments further, by separating logic that don't really belong together. I recommend reading about Cohesion, it's good and fundamental stuff.

Decomposing one longer method to several smaller methods also goes hand in hand with the DRY principle. For example, repeating the print and exit statements is too much work for a lazy (= good) programmer. Add a simple fatal method to make that easier:

private static void fatal(String message) {
    System.out.println(message);
    System.exit(1);
}

Your command line parsing missed an important case: when there are no args.

The parsing and validation can be in a method like this:

private static int getValidPrimeCandidate(String[] args) {
    if (args.length < 1) {
        fatal("Not enough arguments. Please enter a positive integer prime canidate.");
    }

    if (args.length > 1) {
        fatal("Too many arguments. Please enter a positive integer prime canidate.");
    }

    int primeCandidate = 0;
    try {
        primeCandidate = Integer.parseInt(args[0]);
    } catch (NumberFormatException e) {
        fatal("The entered value was not an integer.");
    }

    if (primeCandidate < 0) {
        fatal("Negative numbers are never prime.");
    }
    return primeCandidate;
}

But the biggest problem is of course with the smallestDivisor method. Most importantly, it doesn't do what its name says it does, and consequently its return value needs special interpretation too.

I think a nice solution to that is to make it return the smallest divisor greater than 1. Then, for prime numbers, it will be natural to return the prime number itself. So checking if a candidate is a prime or not becomes checking if its smallest divisor greater than 1 is itself or not.

public static void main(String[] args) {
    int primeCandidate = getValidPrimeCandidate(args);

    if (primeCandidate < 2) {
        System.out.println(primeCandidate + " is neither prime nor composite.");
        return;
    }
    int result = smallestDivisor(primeCandidate);
    if (result == primeCandidate) {
        System.out.println(primeCandidate + " is prime.");
    } else {
        System.out.println(primeCandidate + " is composite and has the smallest divisor " + result + ".");
    }
}

public static int smallestDivisor(int primeCandidate) {
    if (primeCandidate <= 3) {
        return primeCandidate;
    } else if (primeCandidate % 2 == 0) {
        return 2;
    } else if (primeCandidate % 3 == 0) {
        return 3;
    }
    // Checks divisability of numbers in the form of 6k+1 and 6k-1.
    // It starts with: 5 and 7, 11 and 13, 17 and 19, 23 and 25, ...
    for (int i = 5; i * i <= primeCandidate; i += 6) {
        if (primeCandidate % i == 0) {
            return i;
        }
        if (primeCandidate % (i + 2) == 0) {
            return i + 2;
        }
    }
    // No divisor found, the number is prime.
    return primeCandidate;
}

This code can still be improved, as pointed out by other reviews, and by moving the logic out of main, as I suggested above.

Answer 2

Single responsibility principle

You method smallestDivisor() violates the SRP because it does too many things.

It is

• calculating the smallest divisor
• calculating primes
• checking if the number is neither composite nor prime

You should consider to just calculate what the name of the method tells you.

Method names should be made out of a verb or a verb phrase, so getSmallestDivisor() would be better.

So how to handle the edge cases ? That is easy, add methods to evaluate them.

private static boolean isPrime(int number, int smallestDivisor){
    return number == smallestDivisor;
}

private static boolean isComposite(int number, int smallestDivisor){
   return number != smallestDivisor && smallestDivisor > 1;
}

The getSmallestDivisor() method should then return as shown below

public static int smallestDivisor(int primeCandidate) {

    if (primeCandidate =< 1) {
        return primeCandidate;
    }
    if (primeCandidate % 2 == 0) {
        return 2;
    } 
    if (primeCandidate % 3 == 0) {
        return 3;
    } 

    // Checks divisability of numbers in the form of 6k+1 and 6k-1.
    // It starts with: 5 and 7, 11 and 13, 17 and 19, 23 and 25, ...
    for (int i = 5; i <= sqrt(primeCandidate); i += 6) {
        if (primeCandidate % i == 0) {
            return i;
        } else if (primeCandidate % (i + 2) == 0) {
            return i + 2;
        }
    }

    return primeCandidate;
}

to be tested like:

    int smallestDivisor = getSmallestDivisor(primeCandidate);
    if (isPrime(primeCandidate, smallestDivisor)) {
        System.out.println(primeCandidate + " is prime.");
    } else if (isComposite(primeCandidate, smallestDivisor)) {
        System.out.println(primeCandidate + " is composite and has the smallest divisor " + smallestDivisor + ".");
    } else {
        System.out.println(primeCandidate + " is neither prime nor composite.");
    }  

Input

• you haven't checked an edge case: that a user might not pass any argument into the application.
• you should extract the reading of the argument to a separate method and maybe add a possibility, if the given input doesn't match the requirements, to enter the value again. So e.g no arguments provided, value < 0 or not an integer.

Answer 3

1. Since all the if blocks have a return statement, else if is redundant.

2. Divide the main into three parts (just a suggestion):

   • Argument extraction; if success
   • Check if primality candidate; if success
   • Get the smallest divisor.

3. Your method should define 3 states, i.e

   • Neither prime nor composite <1
   • Prime (<4 or otherwise)
   • Composite

   Instead it returns <0, 0, 1, >1. Just a thought for clear definition of the function.

4. Btw,

   if (primeCandidate == 0 || primeCandidate == 1)
   

   is the same as

   if (primeCandidate <= 1)
   

5. Calculate sqrt(primeCandidate) once instead of i*i in every loop. Saves time.

Answer 4

(For reference, I’m posting my resulting code as an answer)

What did I change?

• Moved argument parsing and user input validation to a new method. Thought about seperating these as well but didn’t came up with something suitable.
• The edge cases 0 and 1 are handled directly now (They are neither prime nor composite)
• Honoring the Single Responsibility Principle for getSmallestDivisor() which now only does what it claims to do.
• The for() loop only runs to i <= numberSqrt which is the square root of the prime candidate.
• Little lazyness as suggested by janos: Repeating out.println()’s and exit()’s now have their own little method.

I also looked a bit into javadoc and added @param and @return where I felt they would make sense.

/**
 * Tests a positive integer for primality.
 * Prints out whether a number is prime, composite or neither.
 */
public class PrimalityTest {
    public static void main(String[] args) {
        int primeCandidate = getValidPrimeCandidate(args);

        // Catch `0` and `1` edge cases
        if (primeCandidate < 2) {
            System.out.println(primeCandidate + " is neither prime nor composite.");
            return;
        }

        int smallestDivisor = getSmallestDivisor(primeCandidate);
        if (primeCandidate == smallestDivisor) {
            System.out.println(primeCandidate + " is prime.");
        } else {
            System.out.println(primeCandidate + " is composite and has the smallest divisor " + smallestDivisor + ".");
        }
    }

    /**
     * Validating user input.
     *
     * @param args arguments that were originally passed
     * @return     positive integer prime candidate
     */
    private static int getValidPrimeCandidate(String[] args) {
        if (args.length < 0) {
            fatal("Not enough arguments. Please enter a positive integer prime canidate.");
        }

        if (args.length > 1) {
            fatal("Too many arguments. Please enter a positive integer prime canidate.");
        }

        int primeCandidate = 0;
        try {
            primeCandidate = Integer.parseInt(args[0]);
        } catch (NumberFormatException nfe) {
            fatal("The entered value was not an integer.");
        }

        if (primeCandidate < 0) {
            fatal("Negative numbers are never prime.");
        }

        return primeCandidate;
    }

    /**
     * Returns the smallest divisor of a number greater 1.
     *
     * @param  number                   whose smallest divisor should be returned
     * @throws IllegalArgumentException if number less or equal 1
     * @return                          smallest divisor of the number
     */
    public static int getSmallestDivisor(int number) {
        if (number <= 1) {
            throw new IllegalArgumentException();
        }

        if (number % 2 == 0) {
            return 2;
        }

        if (number % 3 == 0) {
            return 3;
        }

        // Checks divisability of numbers in the form of 6k+1 and 6k-1.
        // Starts with: 5 and 7, 11 and 13, 17 and 19, 23 and 25, ...
        int numberSqrt = (int) Math.round(Math.sqrt(number));
        for (int i = 5; i <= numberSqrt; i += 6) {
            if (number % i == 0) {
                return i;
            }

            if (number % (i + 2) == 0) {
                return i + 2;
            }
        }

        // No divisor found. The number itself is its smallest divisor.
        return number;
    }

    /**
     * A small wrapper to produce error messages
     */
    private static void fatal(String message) {
        System.out.println(message);
        System.exit(1);
    }
}