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

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 opensource, 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 builtin libraries but I think the reasoning could be true for other libraries too.)

You don’t need the parentheses around
number
here:for (int i = 2; i<=(number); i++) {

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 nonrepeating.
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_{1}^{a} * P_{2}^{b} *
P_{3}^{c} * … P_{m}^{m}[P_{1}, P_{2}, P_{3}, … , 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);