Listing a number's prime factors

Question

I wrote a little code to list a number's prime factors:

import java.util.Scanner;
import java.util.Vector;

public class Factorise2
{
    public static Vector<Integer> get_prime_factors(int number)
    {
        //Get the absolute value so that the algorithm works for negative numbers
        int absoluteNumber = Math.abs(number);
        Vector<Integer> primefactors = new Vector<Integer>();
        //Get the square root so that we can break earlier if it's prime

        for (int j = 2; j <= absoluteNumber;)
        {
            //Test for divisibility by j 
            if (absoluteNumber % j == 0)
            {
                primefactors.add(j);
                absoluteNumber /= j;
                if (newprime && j > (int)Math.sqrt(absoluteNumber))
                {
                    break;
                }
            }
            else j++;
        }
        return primefactors;
    }

    public static void main(String[] args)
    {
        //Declare and initialise variables
        int number;
        int count = 1;
        Scanner scan = new Scanner(System.in);
        //Get a number to work with
        System.out.println("Enter integer to analyse:");
        number = scan.nextInt();
        //Get the prime factors of the number
        Vector<Integer> primefactors = get_prime_factors(number);
        //Group the factors together and display them on the screen
        System.out.print("Prime factors of " + number + " are ");
        primefactors.add(0);
        for (int a = 0; a < primefactors.size() - 1; a++)
        {
            if (primefactors.elementAt(a) == primefactors.elementAt(a+1))
            {
                count++;
            }
            else
            {
                System.out.print(primefactors.elementAt(a) + " (" + count + ") ");
                count = 1;
            }
        }
    }
}

I decided that I would try to optimise the algorithm, by skipping testing for divisibility with composite numbers.

import java.util.Scanner;
import java.util.Vector;

public class Factorise2
{
    public static Vector<Integer> get_prime_factors(int number)
    {
        //Get the absolute value so that the algorithm works for negative numbers
        int absoluteNumber = Math.abs(number);
        Vector<Integer> primefactors = new Vector<Integer>();
        Vector<Integer> newprimes = new Vector<Integer>();
        boolean newprime = true;
        int b;
        //Get the square root so that we can break earlier if it's prime

        for (int j = 2; j <= absoluteNumber;)
        {
            //Test for divisibility by j, and add to the list of prime factors if it's divisible. 
            if (absoluteNumber % j == 0)
            {
                primefactors.add(j);
                absoluteNumber /= j;
                if (newprime && j > (int)Math.sqrt(absoluteNumber))
                {
                    break;
                }
                newprime = false;
            }
            else
            {
                for (int a = 0; a < newprimes.size();)
                {
                    //Change j to the next prime
                    b = newprimes.elementAt(a);
                    if (j % b == 0) 
                    {
                        j++;
                        a = 0;
                    }
                    else
                    {
                        a++;
                    }
                }
                //Add j as a new known prime;
                newprimes.add(j);
                newprime = true;
            }
        }
        return primefactors;
    }

    public static void main(String[] args)
    {
        //Declare and initialise variables
        int number;
        int count = 1;
        Scanner scan = new Scanner(System.in);
        //Get a number to work with
        System.out.println("Enter integer to analyse:");
        number = scan.nextInt();
        //Get the prime factors of the number
        Vector<Integer> primefactors = get_prime_factors(number);
        //Group the factors together and display them on the screen
        System.out.print("Prime factors of " + number + " are ");
        primefactors.add(0);
        for (int a = 0; a < primefactors.size() - 1; a++)
        {
            if (primefactors.elementAt(a) == primefactors.elementAt(a+1))
            {
                count++;
            }
            else
            {
                System.out.print(primefactors.elementAt(a) + " (" + count + ") ");
                count = 1;
            }
        }
    }
}

I can't see anything that I have done wrong, but it is much slower. On 9876103, for example, it takes too long to wait for it to report back that its only prime factor is itself. Can anyone see why it is eating CPU cycles?

Answer 1

I decided that I would try to optimise the algorithm, by skipping testing for divisibility with composite numbers.

That is only worthwhile if you factorise a lot of numbers. And then you need to remember the list of known primes between different factorisations.

In your case, the change is a massive pessimisation, because now you check each potential divisor for primality, which in the best case takes one division, and in the worst case about 2*sqrt(j)/log(j) divisions. The worst case, which is common enough, takes much much more time than a simple division by j to check whether j is a divisor.

You have changed the algorithm from O(sqrt(n)) complexity for the simple trial division to about O(n^0.75) (ignoring logarithmic factors) in good cases, and about O(n^1.5) in the worst case (when n is a prime).

Answer 2

Q: Do you know if it's a) "consuming a lot of CPU cycles", or b) just "taking a long time"?

I suspect the latter - that you're underutilizing the CPU ... because you're using (legacy, Java 1.0) "Vector" instead of an ArrayList.

Try ArrayList, and benchmark the difference.

Be sure to look at "Task Mgr" (Windows) or "top" (Linux) to check CPU utilization.

My guess is that you'll have higher CPU usage for the ArrayList version ... and that the ArrayList version will complete sooner :)

IMHO...

Answer 3

I do not think that your algorithm is correct. Try to run it for 24=2*2*2*3 (first version)

I think the sqrt part is not correct. Even more, a sqrt is quite hard to calculate.
Think about it and change it (you can completely remove this part)

After you have fixed it, try to compare both cases, make a small example.
Lets look at 100.

Before:

number = 100
j = 2
100 % 2 = 0, (2)
number = 50
50 % 2 = 0, (2,2)
number = 25
j = 3
j = 4
j = 5
25 / 5 = 5 (2,2,5)
number = 5
5 % 5 = 0 (2,2,5,5)
number = 1
end

After:

number = 100
j = 2
100 % 2 = 0, (2)
number = 50
50 % 2 = 0, (2,2)
number = 25
j = 3
-something is happening
j = 4
-something is happening
j = 5
25 / 5 = 5 (2,2,5)
number = 5
5 % 5 = 0 (2,2,5,5)
number = 1
end

As you see, you just do more work.

And now the last thing: The new version is wrong, too. Try 4 or 9.
And I do not see the idea behind it, so I can not help you there.

For the complexity, see answer from Daniel Fischer.

In general, i would advise to not do any speed optimization until it is really needed and then only for profiled code.