Get prime factors of a given number using Java

Question

I'm trying to get the prime factors of a given number using java.I was able to write following code.It's returning 2,5,10 for the prime factors of 100 while 10 is not a prime number and also it's returning 2,4,11 for the prime factors of 88 wile 4 is not a prime number.Can any one please explain what is the reason and how to fix it?.

import java.util.ArrayList;
import java.util.Random;

public class PrimeFactors {
public static void main(String[] args) {
    Random randomGenarator = new Random();
    int number = randomGenarator.nextInt(150);
    System.out.println("Prime factors of :" + number);
    findPrimeFactors(number);

}

private static void findPrimeFactors(int i) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int n = 2; n <= i; n++) {
        if (i % n == 0) {
            list.add(n);
            i /= n;

        }
    }
    for (int n : list) {
        System.out.println(n);
    }

  }
}

Answer 1

You aren't testing for multiple identical factors in your original number. E.g. when testing 88, you find a 2, but you miss the other 2s. (The number is now 44.) Then you skip to 3 and don't find it. Then you find 4, because 4 is a factor of 44.

You need to keep testing a factor until you no longer find it. Replace the if with while:

while (i % n == 0) {
    list.add(n);
    i /= n;
}

This way you'll find all 2s in the factor before anything else. Then when you get to other composite numbers such as 4 to test, you won't find them.

Answer 2

You are doing it wrong . you need to remove all factors of a prime number before moving on .

for example (pseudo-code)

 if i=100 ,
 continue dividing it by 2 until it is non-divisible 
 i=100/2 =50 , 
 then i=50/2 =25 then stop,
 then look for next prime.

Hope it helps.