Fast factoring algorithms? [closed]

Question

How can I quickly find all factors of a number?

e.g.:

digit: 20
factors: {1*20, 2*10, 4*5, 5*4, 10*2, 20*1}

Answer 1

This is actually a problem for which no good solution is known. For this reason, RSA encryption actually depends on the computational difficulty of factoring numbers. See: Integer Factorization

However, you may be able to speed up the algorithms already given by only looking at numbers up to the square root of n, and checking if they are factors by checking if n % i == 0. If this is true, you can find the corresponding factor greater than n^(.5) by taking n / i.

Answer 2

If the number that you want to find the factors for happens to be odd, you only need to test odd numbers because it is impossible to have an even factor for an odd number. So with a pre-check up front, you can save yourself some processing.

private static List<Integer> findFactors(int num)
{
    int incrementer = 1;
    if (num % 2 != 0)
    {
        incrementer = 2; //only test the odd ones
    }
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 1; i <= num / 2; i=i+incrementer)
    {
        if (num % i == 0)
        {
            list.add(i);
        }
    }
    list.add(num);
    return list;
}

Answer 3

Go through a loop applying modulus to all of the intermediate numbers.

X=1;
WHILE(X<=20)
 IF 20%x == 0
 THEN FACTOR!
 X++;
END