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?
Vector
as it issynchronized
. Use an unsynchronized Collection class likeArrayList
or similar. \$\endgroup\$