# Factorizing integers

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

-

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

-
That's great, it's an improvement. About primeFactors(), would it be better to use that method, instead of my original post? – Leonardo Chaia Feb 25 '14 at 17:58
@LCH: It depends on the requirements/context. If I could I would use the Apache library to reduce maintenance work but there might be legal or other constraints. (Furthermore, I guess they are better on primes than me. Read the Effective Java chapter, it contains a lot of arguments to consider.) It's open-source, so you can copy just the relevant parts of the library code (there might be licence restrictions). – palacsint Feb 25 '14 at 18:10
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. – Will Ness Mar 1 '14 at 4:25
@WillNess: Good point, thanks! It deserves an answer. Would you write it? – palacsint Mar 1 '14 at 11:51

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.

-
+1, You're right, I've missed that number is modified during the loop. – palacsint Feb 25 '14 at 21:52
The rise of jarnbjo... ;) Come visit us over in our chat room sometime. – syb0rg Feb 25 '14 at 22:04
"Better factorizing algorithms than this brute force approach are not known."; of course there are! In the context (31-bit numbers), I would recommend Pollard's rho – fgrieu Feb 25 '14 at 22:19
@fgrieu: Isn't Pollard's rho algorithm indeterminate? It is perhaps suitable to search for a factor, given that it is acceptable that the algorithm stops when no factor has been found within a reasonable time, but at least in theory, the algorithm may run forever without finding a correct factor. – jarnbjo Feb 25 '14 at 22:54
You are correct that Pollard's rho is a probabilistic algorithm; yet using it allows enormous speedup in practice in the average case, and it is possible to make a deterministic algorithm using some trial division, and say 30% of the effort on a derandomized Pollard's rho, that will at worst take 1/(1-30%)=143% of the time of trial division, and much less than 100% on average. Even if we want to stick to fully deterministic algorithms, there are variants of Fermat factoring, like this – fgrieu Feb 26 '14 at 7:17

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);
}
}

-
i*i is faster than sqrt, is what is commonly said. – Will Ness Mar 1 '14 at 12:41
@WillNess: I know that (note the word solution in the original text;) but I was not sure because sqrt is inside the while loop and might have not run the same times as i*i. – palacsint Mar 1 '14 at 12:51
it's good if you test this, then we'd know for sure. I'm just saying, Ive seen it stated several times that using the i*i way is faster than the other way. – Will Ness Mar 1 '14 at 12:54

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)