# Factorizing integers

Posted on

Problem

I’m working on this method in Java, which is giving me the factors of a number. I’ll be using this method a lot, and I was wondering if there isn’t a better way of doing it. Like, with just one loop. Although this code works great and it returns what I expect, I just want to know if there’s a better workaround.

The method:

``````public static void main(String[] args) {
System.out.print("Enter a positive number: ");
Scanner scanner = new Scanner (System.in);
int number = scanner.nextInt();
int count;
for (int i = 2; i<=(number); i++) {
count=0;
while (number % i == 0) {
number /= i;
count++;
}
if (count == 0) continue;
System.out.println(i+ "**" + count);
}
}
``````

The output I’m expecting:

``````number = 288;
2**5
3**2
``````

Solution

1. Apache Commons Math has a similar function: `Primes.primeFactors()`

``````Primes.primeFactors(288)
``````

Returns a list with the following elements:

``````[2, 2, 2, 2, 2, 3, 3]
``````

It open-source, check the implementation (source1, source2) and it contains a lot of optimization. (For example, instead of iterating it all of the numbers, at the beginning it uses an array with the first 512 primes to make it faster.)

So it seems faster but it needs some additional work if you want to use your original format. (Converting the list to the `P**F` format.

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries The author mentions only the JDK’s built-in libraries but I think the reasoning could be true for other libraries too.)

2. You don’t need the parentheses around `number` here:

``````for (int i = 2; i<=(number); i++) {
``````
3. This kind of formatting is very hard to read:

``````if (count == 0) continue;
System.out.println(i+ "**" + count);
``````

It looks like that `println` would depend on the condition.

(According to the Code Conventions for the Java Programming Language `if` statements always should use braces.)

Even if looping from `2` to `sqrt(number)` is an optimization as suggested by palacsint, you would run better by looping as long as `number > 1`:

``````for (int i = 2; number > 1; i++) {
...
}
``````

Since you are only working on relatively small numbers (`Integer.MAX_VALUE` or less), you should also consider using a prime number table instead of trying each and every divisor from `2` to `sqrt(number)`. There are roughly 4.800 prime numbers less than `sqrt(Integer.MAX_VALUE)`, which cover all possible factors. Keeping them in an array of ints and testing only those numbers as possible factors should also gain some performance.

Better factorizing algorithms than this brute force approach are not known.

To summarize Will Ness‘s comment:

no, you still have to loop to the square root
of the (updated) number, only. Because it might
be a prime. And it will be, if the largest
prime factor of original number is non-repeating.

Here is an updated method:

``````public static List<Integer> factorize(int number) {
final List<Integer> factors = newArrayList();
for (int i = 2; i * i <= number; i++) {
while (number % i == 0) {
number /= i;
}
}
if (number > 1) {
}
return factors;
}
``````

It’s possible to change multiplication in `i * i <= number` to square root:

``````public static List<Integer> factorize2(int number) {
final List<Integer> factors = newArrayList();
int root = (int) Math.sqrt(number);
for (int i = 2; i <= root; i++) {
while (number % i == 0) {
number /= i;
root = (int) Math.sqrt(number);
}
// root = (int) Math.sqrt(number); // sqrt could be here also
}
if (number > 1) {
}
return factors;
}
``````

I haven’t done any performance test (nor checked the O of `sqrt`) to decide which solution is faster. (I still would use Apache Commons Math.)

The method was modified to return a list of factors instead of printing them for easier testing:

``````@Test
public void testFactorize() {
for (int i = 2; i < 100000; i++) {
final List<Integer> factors = PrimeFactor.factorize(i);
final List<Integer> expectedFactors = Primes.primeFactors(i);
assertEquals("" + i, expectedFactors, factors);
}
}
``````

which is giving me the factors of a number

Since english is not your native language I think you meant to say prime factors of a number. However if you want to get number of factors for a number, your method will help you. Since any number can be written as multiple of prime number the number of factor of a prime number can be written as

N = P1a * P2b *
P3c * … Pmm

[P1, P2, P3, … , Pm are
all prime number]

then

number of divisors

d(N) = (a+1) * (b+1) * (c+1) … (m+1)

There is only one `continue` with one `if` so you can guess `continue` is redundant.
``````if (count != 0)