Number factor of a number

Question

I currently have a number factors program that performs the following things: The user enters a number, checks whether it is a perfect square (yes or no), prints the square root if it is a perfect square, determining the number if it is prime or not, and the number factors of that specific number.

import java.util.Scanner;
import java.util.Date;
import java.text.SimpleDateFormat;

public class NumberFacts {

public static void main(String[] args) {
    // Initialize the Scanner
    Scanner in = new Scanner(System.in);

    //Prompt the user to input the number to evaluate
    System.out.print("Enter a number (from 1 to 10000): ");

    // Store the input number 
    int myNum = in.nextInt();

    SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss");
    Date start = new Date();

    startProcess(start);

    System.out.println("\nNumber\tPerfect Sqr\tSqrt\tPrime\tFactors");

    // For each number iteration, we should begin by bringing a pair each
    // time until we hit that number.
    iterNum(myNum);

    in.close();

    Date stopTime = new Date();
    long diff = stopTime.getTime() - start.getTime();

    stopProcess(dateFormat, start, stopTime, diff);

} // end of main method

 private static void iterNum(int n) {
    for (int iter = 1; iter <= n; iter++) {

        // Start the factorPair as an empty string
        String factorPair = "";

        // Initialize the loop counter.
        int i = 1;

        // Result returns the number the user entered.
        int result = iter;

        // Used to store for pairs.
        String myPairs = "";

        // Main counter for our pairs.
        int pairsCounter = 0;

        // Initialize square root variable with 0.
        int sqrt = 0;

        // Initialize factor variables
        int factor1;
        int factor2;

        // Begin factoring pairs
        do {

            if (iter % i == 0) {
                // Starts with the initial number
                // until the last number the user
                // specified.
                factor1 = i;

                // We divide each number by 1 and
                // truncate each number to have a
                // precise number.
                factor2 = iter / i;

                // If the number is a factor pair, then
                // output the number.
                if (factor1 <= factor2) {
                    factorPair = "(" + factor1 +", "+ factor2 + ")";
                    pairsCounter++;
                    myPairs += factorPair;
                }

                // Checks whether the number is a square root
                // number that will assume either yes
                // or no.
                if (factor1 == factor2) {
                    sqrt = factor1;
                }
            }

        } while (++i <= result); // End of the factoring pair loops.

        // Print the expected formatted output for the program.
        printOutput(iter, sqrt, pairsCounter, myPairs);
    }
 }

 private static void startProcess(Date s) {
    System.out.println("Started processing at " + s);
 }

 private static void stopProcess(SimpleDateFormat d, Date n1, Date n2, long l) {
    System.out.println("\n\nStart processing " + d.format(n1) + "\n\nStop processing: " + d.format(n2) + "\n\nDifference: " + l + " ms");
 }

 private static void printOutput(int a, int sq, int c, String s) {
    System.out.printf("%n %d \t%s\t\t%s\t%s\t%s", a, sq > 0 ? "Yes" : "No", sq > 0 ? Integer.toString(sq) : "", c > 1 ? "No" : "Yes", s);
 }

} // end of class

When compiled and start it, I do the following:

Enter a number (from 1 to 10000): 25
Started processing at Tue Sep 11 22:03:30 CDT 2018

Number    Perfect Sqr     Sqrt    Prime   Factors

1         Yes             1       Yes     (1, 1)
2         No                      Yes     (1, 2)
3         No                      Yes     (1, 3)
4         Yes             2       No      (1, 4)(2, 2)
5         No                      Yes     (1, 5)
6         No                      No      (1, 6)(2, 3)
7         No                      Yes     (1, 7)
8         No                      No      (1, 8)(2, 4)
9         Yes             3       No      (1, 9)(3, 3)
10        No                      No      (1, 10)(2, 5)
11        No                      Yes     (1, 11)
12        No                      No      (1, 12)(2, 6)(3, 4)
13        No                      Yes     (1, 13)
14        No                      No      (1, 14)(2, 7)
15        No                      No      (1, 15)(3, 5)
16        Yes             4       No      (1, 16)(2, 8)(4, 4)
17        No                      Yes     (1, 17)
18        No                      No      (1, 18)(2, 9)(3, 6)
19        No                      Yes     (1, 19)
20        No                      No      (1, 20)(2, 10)(4, 5)
21        No                      No      (1, 21)(3, 7)
22        No                      No      (1, 22)(2, 11)
23        No                      Yes     (1, 23)
24        No                      No      (1, 24)(2, 12)(3, 8)(4, 6)
25        Yes             5       No      (1, 25)(5, 5)

Start processing 2018/09/11 22:03:30

Stop processing: 2018/09/11 22:03:30

Difference: 13 ms

It runs fast with small numbers but when it comes to bigger numbers such as 6000 to 10000, the speed gets slower with the difference from the start to finish. Inputting 10,000 numbers averages around 800 to 900ms each run.

How can I improve the speed of the computation time in each program run?

Answer 1

The most important improvement is that you can abort your loop as soon as factor1 becomes greater than factor2, effectively only iterating up to your number's square root instead of the whole way.

Another local improvement is to avoid repeated String concatenations. Repeatedly concatenating another pair of factors to the end of a String always creates a new String and throws away the previous intermediate String. For this purpose, StringBuilder is better.

An improved version of your program goes like this:

package test;

import java.util.Scanner;
import java.util.Date;
import java.text.SimpleDateFormat;

public class NumberFacts {

    public static void main(String[] args) {
        // Initialize the Scanner
        Scanner in = new Scanner(System.in);

        //Prompt the user to input the number to evaluate
        System.out.print("Enter a number (from 1 to 10000): ");

        // Store the input number 
        int myNum = in.nextInt();

        SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss");
        Date start = new Date();

        startProcess(start);

        System.out.println("\nNumber\tPerfect Sqr\tSqrt\tPrime\tFactors");

        // For each number iteration, we should begin by bringing a pair each
        // time until we hit that number.
        iterNum(myNum);

        in.close();

        Date stopTime = new Date();
        long diff = stopTime.getTime() - start.getTime();

        stopProcess(dateFormat, start, stopTime, diff);

    } // end of main method

    private static void iterNum(int n) {
        for (int iter = 1; iter <= n; iter++) {
            analyzeNumber(iter);
        }
    }

    private static void analyzeNumber(int numberUnderTest) {
        int factor1 = 1;
        int factor2 = numberUnderTest;
        int pairsCounter = 0;
        int sqrt = 0;
        StringBuilder myPairs = new StringBuilder();

        // Begin factoring pairs
        do {
            if (numberUnderTest % factor1 == 0) {
                factor2 = numberUnderTest / factor1;

                // If the number is a factor pair, then
                // output the number.
                if (factor1 <= factor2) {
                    String factorPair = "(" + factor1 +", "+ factor2 + ")";
                    pairsCounter++;
                    myPairs.append(factorPair);
                }

                // Checks whether the number is a perfect square 
                if (factor1 == factor2) {
                    sqrt = factor1;
                }
            }

        } while (++factor1 <= factor2); // End of the factoring pair loops.

        // Print the expected formatted output for the program.
        printOutput(numberUnderTest, sqrt, pairsCounter, myPairs.toString());
    }

    private static void startProcess(Date s) {
        System.out.println("Started processing at " + s);
    }

    private static void stopProcess(SimpleDateFormat d, Date n1, Date n2, long l) {
        System.out.println("\n\nStart processing " + d.format(n1) + "\n\nStop processing: " + d.format(n2) + "\n\nDifference: " + l + " ms");
    }

    private static void printOutput(int a, int sq, int c, String s) {
        System.out.printf("%n %d \t%s\t\t%s\t%s\t%s", a, sq > 0 ? "Yes" : "No", sq > 0 ? Integer.toString(sq) : "", c > 1 ? "No" : "Yes", s);
    }

} // end of class

It reduces the run time for 100000 numbers from 25 seconds (original program) to 6 seconds on my machine.

Besides the optimizations, I also made the program more readable to me ;-):

• I extracted the analysis of a single number into a method of its own.
• I merged a few duplicate variables into one, e.g. i and factor1 always have the same value, so there's no need to have both.
• I renamed iter to numberUnderTest.
• I had my favourite IDE (Eclipse) indent the code (mark all, Ctrl-Shift-I).

Finally, the algorithm you chose is a straightforward one: try all potential factors until you have them all. There are faster, more complex ones. Just to give you an idea:

Do a factorization of your number into prime factors. Then you can separate the list of prime factors into two parts, one giving factor1, and the other factor2. Enumerate all the possible separations, and you get all factor pairs. While you're doing the factorization for all the numbers under test, beginning with 1, you can memorize and re-use the factorizations, e.g. when you found that 12=2*2*3, and then get to test the number 24, you divide by 2, find the result 12, know that 12=2*2*3, so we immediately know that 24 = 2 * 2*2*3 without having to analyze the 12 again.

But as long as you don't plan to factorize numbers with 100 digits or so, you probably won't need the most sophisticated algorithm.

To comment on Sharon's suggestion on using multiple threads: your algorithm analyzes every number in isolation, so multiple threads can independently run with individual numbers, meaning that your program is a candidate well-suited for multi-threading. This has the potential to reduce your execution time by the number of CPU cores in your hardware (as long as you're alone on an otherwise idle system). But managing multi-threaded programs can be a challenge, even to experienced Java programmers.

Answer 2

Seems to me that the program is a good fit for multi threaded processing:

1. Set up a thread pool with a fixed number of threads. Usually it is connected to the number of processors of your hardware.
2. Split the range of iteration by the number of threads in the pool. invoke each thread and give it its range to work on.
3. After all threads have finished, they report the results back to the main thread and it does the printing, so it gets printed in order.

I suggest you work with Java's ExecutorService that manages thread pools, tasks and fork/join framework.