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

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;
            factors.add(i);
        }
    }
    if (number > 1) {
        factors.add(number);
    }
    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;
            factors.add(i);
            root = (int) Math.sqrt(number);
        }
        // root = (int) Math.sqrt(number); // sqrt could be here also
    }
    if (number > 1) {
        factors.add(number);
    }
    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 = P₁^a * P₂^b *
P₃^c * … P_m^m

[P₁, P₂, P₃, … , P_m are
all prime number]

then

number of divisors

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

More reading from MathsChallenge.

_{Leaving implementation as your homework}

There is only one continue with one if so you can guess continue is redundant.

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