# Listing a number's prime factors

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)
{
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 ");
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)
{
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;
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 ");
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?

-

## migrated from stackoverflow.comNov 19 '12 at 17:43

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

By a glance: you have nested loops in second version. –  Suzan Cioc Nov 17 '12 at 18:54
Do not use Vector as it is synchronized. Use an unsynchronized Collection class like ArrayList or similar. –  nkr Nov 17 '12 at 18:55
Use Sieve of Eratosthenes. –  Rezo Megrelidze Oct 7 '14 at 16:11

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

-

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

-
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
@tb You can use procexp.exe for that. you can download it from here: technet.microsoft.com/en-us/sysinternals/bb896653.aspx –  Rezo Megrelidze Oct 7 '14 at 16:27

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.

-