Factor 999999 numbers as fast as possible

Question

My code finds the prime factorization of numbers, ordering the prime numbers from least to greatest. It prints a list of 999999 prime factorizations (which can be changed if you edit the function call in the main method). I'm thinking that maybe the string concatenation is the most expensive operation because Java Strings are immutable, meaning they must be destroyed and reconstructed every time their value is changed. I'm not quite sure how to connect strings without concatenation. I am also wondering if I am missing any optimizations with the math algorithm itself. Note that I am already aware that you only need to check up to the square root of a number for prime factors, that's in my code.

Thanks, here is my code (written in Java in the IDE Eclipse).

public class Prime {
    public static void main (String [] args) {
        factorList(999999);
    }
    public static boolean isPrime(int x) {
        if (x == 1) return false;
        for (int i = 2; i<= Math.sqrt(x); i++) {
            if (x % i == 0 && i != x) {
                return false;
            }
        }
        return true;
    }
    public static int factor (int x) {
        for (int i = 2; i<= Math.sqrt(x); i++) {
            if (x % i == 0 && i != x) {
                return i;
            }
        }
        return -1;
    }
    public static void factorList (int x) {
        if (x<=1) {
            throw new IllegalArgumentException("1 & negative numbers are neither prime nor composite");
        }
        for (int i = 2; i<= x; i++) {
            if (isPrime(i)) {
                System.out.println(i +" is a prime number, can't be factored");
            } else {
                System.out.println(i+ " is a composite number: " + factor(i) + " * " + (i/factor(i)));
            }
        }
    }
    public static void factorList (int [] x) {
        for (int i = 0; i< x.length; i++) {
            if (isPrime(x[i])) {
                System.out.println(x[i] +" is a prime number, can't be factored");
            } else {
                System.out.println(x[i]+ " is a composite number: " + factor(x[i]) + " * " + (x[i]/factor(x[i])));
            }
        }
    }
    public static void primeFactorize (int x) {
        if (isPrime(x)) {
            System.out.print(x);
        } else {
            System.out.print(factor(x)+ "*");
            primeFactorize(x/factor(x));
        }
    }
}

Answer 1

You have functions factorList(int[]) and primeFactorize(int) that are both unused.

You also have an isPrime(int) function that basically does the same work as factor(int), but throws away some information. Therefore, whenever you detect a non-prime number, you end up doing the same work twice to show a factorization. In both of those functions, the conditional if (x % i == 0 && i != x) contains a redundant && i != x test that should never be true.

x has a connotation of being a floating-point number; it would be more conventional to use n for integers.

So far, then, we have:

public class Prime {

    public static void main (String [] args) {
        factorList(999999);
    }

    /**
     * Returns the smallest factor of n that is greater than 1.
     * Returns n, if n is prime.
     */
    public static int factor(int n) {
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return i;
            }
        }
        return n;
    }

    public static void factorList(int n) {
        if (n <= 1) {
            throw new IllegalArgumentException("1 & negative numbers are neither prime nor composite");
        }
        for (int i = 2; i <= n; i++) {
            int j = factor(i);
            if (i == j) {
                System.out.println(i + " is a prime number, can't be factored");
            } else {
                System.out.println(i + " is a composite number: " + j + " * " + i / j);
            }
        }
    }
}

---

If you want to classify the first n numbers as prime or composite quickly, though, you should use the sieve-of-eratosthenes. That can do the job with no multiplication or square roots!

Answer 2

Timing tests

I'm thinking that maybe the string concatenation is the most expensive operation because Java Strings are immutable

This is easy to test. Just time it.

long start = System.nanoTime();
factorList(999999);
System.out.println(System.nanoTime() - start);

Now make a new method that doesn't concatenate.

            System.out.println(" is a prime number, can't be factored");
        } else {
            System.out.println(" is a composite number: ");

with

start = System.nanoTime();
factorListNoConcatenation(999999);
System.out.println(System.nanoTime() - start);

Was it slower in fact? I realize that it may return incorrect output. But the question is if concatenation was the primary source of slowness. If the two are approximately the same speed, then your surmise was incorrect.

Hint: I would expect the printing to be slower than the string concatenation. But you don't need to rely on my guess. Test it.

Note that there is more we can say about timing. But I'm not going to try to do that here. Feel free to ask a follow up question that includes timing code, and people will be able to give you more advice. For example, on priming your tests and repeating them.

Algorithmic improvements

For some value of n (and 999999 may be below that value), the most expensive operation will be the isPrime method.

You have

        if (x == 1) return false;
        for (int i = 2; i<= Math.sqrt(x); i++) {

There are some simple things that you can do with just those. I would say

        if (x <= 1) {
            return false;
        }

Then if someone does pass zero or a negative number, you give an accurate response. You may know that that will never happen, but in this case, you don't save anything with that assumption. It's generally as easy to check a range as equality. Both are just one comparison. You can do a timing test to verify that, but I would expect this code to be just as fast.

For another thing, you could add

        if (x <= 3) {
            return true;
        }
        if (x % 2 == 0) {
            return false;
        }

and then change the loop to

        int limit = Math.sqrt(x);
        for (int i = 3; i <= limit; i += 2) {

Moving the square root operation out of the loop may not do anything, as the compiler may do that for you. You can do a timing test to see. But you certainly don't want to take the square root on every iteration, as a square root is an expensive operation. So if you are looking for speed, you should at least try it.

Note that on many processors, it's just as fast to say

        for (int i = 3; i <= x / i; i += 2) {

Because the next line tests x % i and many processors calculate both the quotient and the remainder in the same operation. So if you're already calculating one, the other is free. Again, you can do a timing test to see if it is faster to skip the square root.

Once we've tested 2, we don't every need to test another even number. Because if it's not divisible by 2, it's not divisible by any even number. So we can cut our loop iterations almost in half by only checking the odd numbers.

So for 1 and under, we return false. For 2 and 3 (because we already returned for anything less), we return true. For all even numbers greater than two, we return false. Now we just need to test odd numbers 3 and up. That's what this version of the loop does.

We could continue this with three if we wanted (although that makes the isPrime method more complicated, as we have to change the increment on each iteration). But you've already been advised to consider a sieve. That just continues the same principle. There is no point in testing non-prime factors. You can sieve them out (as we sieved out the even numbers here). And you are already generating all the potential smaller prime factors. So why not take advantage of that?