patternjavaModerate
Factorizing integers
Viewed 0 times
integersfactorizingstackoverflow
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:
The output I'm expecting:
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**2Solution
Even if looping from
Since you are only working on relatively small numbers (
Better factorizing algorithms than this brute force approach are not known.
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.
Code Snippets
for (int i = 2; number > 1; i++) {
...
}Context
StackExchange Code Review Q#42786, answer score: 10
Revisions (0)
No revisions yet.