Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I wrote a little ditty 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?

share|improve this question
1  
By a glance: you have nested loops in second version. –  Suzan Cioc Nov 17 '12 at 18:54
4  
Do not use Vector as it is synchronized. Use an unsynchronized Collection class like ArrayList or similar. –  nkr Nov 17 '12 at 18:55
add comment

migrated from stackoverflow.com Nov 19 '12 at 17:43

This question came from our site for professional and enthusiast programmers.

3 Answers

up vote 8 down vote accepted

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).

share|improve this answer
add comment

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...

share|improve this answer
    
They both max out the CPU, and both are equally slow. –  user1774214 Nov 17 '12 at 19:10
    
you can not see cpu cycles in task manager or top. and even if you see cpu cycles, you do not know the load factor for modern cpus. For java, focus on algorithms, not cpu optimizations. –  tb- Nov 23 '12 at 16:49
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.