Prime factorization of a natural number greater than 1

Question

I want to write a program in Java that return a prime factorization of any natural number greater than one.

After spending some time coding and debugging, the program runs fine. Since I am new to Java and programming in general, I don't know how bad my code style and class/method design are. Hence, I am here asking for some tips/advice on what I did wrong and what I could do to improve.

public class FTA_Prime_Factorization {

    /**
     * A method to ask for a integer input from user.
     *
     * @return num: int
     */
    protected static int user_input() {
        int num;
        Scanner inp;
        while (true) {
            inp = new Scanner(System.in);
            System.out.print("Please enter a greater-than-1 positive integer: #");
            if (inp.hasNextInt() && (num = inp.nextInt())>1)
                break;
            System.out.println("Please enter a integer greater than 1!!!");

        }
        return num;
    }

    /**
     * To check whether the parameter is a prime number.
     *
     * @param x: int
     * @return counts == 2: boolean
     */
    private static boolean checkPrime (int x) {
        int counts = 0;
        for (int i = x; i > 0; i--) {
            if (x % i == 0) {
                counts++;
            }
        }
        return counts == 2;
    }

    /**
     * To create an Arraylist of prime number that is less than 10000.
     *
     * @return primeList: Arraylist<Integer>
     */
    private static ArrayList<Integer> primes() {
        ArrayList<Integer> primeList = new ArrayList<>();
        for (int x = 1; x < 10000; x++){
            if (checkPrime(x))
                primeList.add(x);
        }
        return primeList;
    }

    /**
     * To create an Arraylist of prime factorization of the parameter.
     *
     * @param x: int
     * @return primeFactors: Arrarylist<Integer>
     */
    private static ArrayList<Integer> array(int x) {
        ArrayList<Integer> primeFactors = new ArrayList<>();
        ArrayList<Integer> listOfPrime = primes();
        for (int i : listOfPrime) {
            for (int j = x; j % i== 0; j /= i)
                primeFactors.add(i);
        }
        return primeFactors;
    }


    public static void main(String [] args) {
        ArrayList<Integer> temp = array(user_input());
        HashMap<Integer, Integer> counter = new HashMap<>();
        String primeFactors = "";
        for (int element : temp) {
            if (counter.get(element) != null){
                counter.put(element, counter.get(element)+1);
            }else{
                counter.put(element, 1);
            }
        }
        System.out.print("Canonical Form Prime factorization of x = ");
        for (int key : counter.keySet()) {
            primeFactors += counter.get(key) == 1 ? "(prime)"+key + " x " : "(prime)"+key+"^"+counter.get(key) + " x ";
        }
        System.out.println(primeFactors.substring(0, primeFactors.length() - 3));
    }
}

An example output (input = 3612):

Canonical Form Prime factorization of x = (prime)2^2 x (prime)3 x (prime)7 x (prime)43

Answer 1

Method names

You should try to make the name of your methods are descriptive as possible, without being too long:

• user_input should first be userInput according to Java naming conventions. But it is difficult to tell what the method does by just looking at its name: it surely involves the user input but we don't know how and why. In this case, the purpose of the method is to retrieve a number to factor. A possible name would be getNumberToFactor or askNumberToFactor, although I would prefer the first variant because it describes what the method does and does not care of how it does it: in the future, you might expand this code and read the number from a file for example; the method's purpose would still be the same, and its name wouldn't change.
• checkPrime could be renamed isPrime: generally, boolean-returning methods have a name starting with is (or has).
• primes is fine: it returns a list of prime numbers and it is well described that this name. (Perhaps getPrimes() but this is a matter of opinion)
• array is misleading. One would assume that it makes an array of something when it fact, this is the prime method making the factorization. It would be better to name it primeFactors and make it clear that this method makes the prime factorization of the given parameter.

Programming to an interface

It is a good idea to program to an interface. This means, trying to avoid the implementing classes and work only on the interfaces. In this case, you are passing ArrayList when you should be passing List:

           //  v--v
private static List<Integer> primes() {
    List<Integer> primeList = new ArrayList<>();
 // ^--^
    for (int x = 1; x < 10000; x++){
        if (checkPrime(x))
            primeList.add(x);
    }
    return primeList;
}

    Map<Integer, Integer> counter = new HashMap<>();
//  ^-^

Separated logic

You have reasonably well separated the code into methods, but the main array is missing its main ingredient. This method is the central-point for making the prime factorization. Therefore, it is that method that should direcly return a Map<Integer, Integer> of the prime factors with their exponent.

Currently, this code is separated in two unrelated blocks:

private static ArrayList<Integer> array(int x) {
    // return list of primes dividing x
}

public static void main(String [] args) {
    ArrayList<Integer> temp = array(user_input());
    HashMap<Integer, Integer> counter = new HashMap<>();
    // process that list and turn it into a Map
}

Note that separating this code actually hides you from an optimization you can make: you don't need to have a list of all primes factors with duplicate values. You can just construct the Map directly, without having that temporary list:

private static Map<Integer, Integer> primeFactors(int x) {
    Map<Integer, Integer> primeFactors = new HashMap<>();
    ArrayList<Integer> listOfPrime = primes();
    for (int i : listOfPrime) {
        for (int j = x; j % i == 0; j /= i) {
            if (primeFactors.get(i) != null) {
                primeFactors.put(i, primeFactors.get(i) + 1);
            } else {
                primeFactors.put(i, 1);
            }
        }
    }
    return primeFactors;
}

If you're using Java 8, you can make this even simpler by replacing the updating of the map with counter.merge(i, 1, Integer::sum);:

private static Map<Integer, Integer> array(int x) {
    Map<Integer, Integer> counter = new HashMap<>();
    ArrayList<Integer> listOfPrime = primes();
    for (int i : listOfPrime) {
        for (int j = x; j % i == 0; j /= i) {
            counter.merge(i, 1, Integer::sum);
        }
    }
    return counter;
}

Avoid concatenating Strings with +=

In the following loop

for (int key : counter.keySet()) {
    primeFactors += counter.get(key) == 1 ? "(prime)" + key + " x "
            : "(prime)" + key + "^" + counter.get(key) + " x ";
}

you are concatenating the primeFactors variables with +=. This is not a good practice because it creates a lot of Strings in memory. It would be better to use a StringBuilder for this task and append each part with append(...).

Also, I don't see the need to print (prime) each time: you know it's a prime already since we're doing the prime factorization.

If you're using Java 8, you can actually use StringJoiner instead: this will also enable you to get rid of the

primeFactors.substring(0, primeFactors.length() - 3)

at the end. This class is designed to join Strings together with a separator:

StringJoiner sj = new StringJoiner(" ");
for (int key : counter.keySet()) {
    sj.add(counter.get(key) == 1 ? key + " x" : key + "^" + counter.get(key) + " x");
}
System.out.println(sj.toString());

Answer 2

In addition to the excellent points raised by @Tunaki...

try-with-resources

You should use try-with-resources on the Scanner instance when reading user input for safe and efficient handling of the underlying I/O resource.

A better prime detection algorithm

private static boolean checkPrime (int x) {
    int counts = 0;
    for (int i = x; i > 0; i--) {
        if (x % i == 0) {
            counts++;
        }
    }
    return counts == 2;
}

This is a very simplistic way of finding primes, and since you are coming in with math background, I'm sure there's some areas of improvement here. :)

• You don't have to keep counting all the factors until the end of the loop to check if you have only two factors. Such checks can be done inside the loop, i.e. if counts > 2, you can immediately return false from the method.
• You also don't have to loop through each number lesser than x, the usual recommendation is to reach the square root of x, and you can quit if there's no other factors other than 1, or the number itself.

Here's a slightly optimized version for comparison:

public static boolean isPrime(int x) {
    if (x < 2) {
        return false;
    }
    for (int i = 2; i <= (int) Math.sqrt(x); i++) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

• Any negative numbers, and the numbers \$0\$ and \$1\$ are not primes.
• Loop upwards starting from \$2\$ to the integer value of \$\sqrt{x}\$ inclusive to see if there are any factors here. If so, we know that there's an additional pair besides \$1, x\$ and therefore return false.
• Otherwise, this is indeed a prime number.

Using the first 3-digit prime number, 101 as an example, your implementation will have to loop through 101 times to count that there's only 2 factors, \$1, 101\$. With the slightly optimized method, we only need to loop 9 times (\$[2 ... 10]\$) to determine that there's no other factors.

What you really should be looking into though is something like the Sieve of Eratosthenes, so that you can skip checking for certain numbers entirely. For example, once you have established that 3 is a prime number, you can ignore all multiples of 3 as they are non-prime themselves.