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?
Listing a number's prime factors
java;performance;beginner;primes
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).