Best Way to Find All Factors of a Given Number

Best way to find all factors of a given number

pseudocode:

• Loop from 1 to the square root of the number, call the index "i".
• if number mod i is 0, add i and number / i to the list of factors.

realocode:

public List<int> Factor(int number) 
{
    var factors = new List<int>();
    int max = (int)Math.Sqrt(number);  // Round down

    for (int factor = 1; factor <= max; ++factor) // Test from 1 to the square root, or the int below it, inclusive.
    {  
        if (number % factor == 0) 
        {
            factors.Add(factor);
            if (factor != number/factor) // Don't add the square root twice!  Thanks Jon
                factors.Add(number/factor);
        }
    }
    return factors;
}

As Jon Skeet mentioned, you could implement this as an IEnumerable<int> as well - use yield instead of adding to a list. The advantage with List<int> is that it could be sorted before return if required. Then again, you could get a sorted enumerator with a hybrid approach, yielding the first factor and storing the second one in each iteration of the loop, then yielding each value that was stored in reverse order.

You will also want to do something to handle the case where a negative number passed into the function.

What is the most efficient way of finding all the factors of a number in Python?

from functools import reduce

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

This will return all of the factors, very quickly, of a number n.

Why square root as the upper limit?

sqrt(x) * sqrt(x) = x. So if the two factors are the same, they're both the square root. If you make one factor bigger, you have to make the other factor smaller. This means that one of the two will always be less than or equal to sqrt(x), so you only have to search up to that point to find one of the two matching factors. You can then use x / fac1 to get fac2.

The reduce(list.__add__, ...) is taking the little lists of [fac1, fac2] and joining them together in one long list.

The [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 returns a pair of factors if the remainder when you divide n by the smaller one is zero (it doesn't need to check the larger one too; it just gets that by dividing n by the smaller one.)

The set(...) on the outside is getting rid of duplicates, which only happens for perfect squares. For n = 4, this will return 2 twice, so set gets rid of one of them.

Most Efficient Way to Find All the Factors of a Number?

Most Python methods in the referenced Q&A What is the most efficient way of finding all the factors of a number in Python? use the fact that
factors of n come in pairs: if i is a factor then n/i is another
factor. Therefore it is sufficient to test factors up to the square root
of the given number.

Here is a possible implementation in Swift:

func factors(of n: Int) -> [Int] {
    precondition(n > 0, "n must be positive")
    let sqrtn = Int(Double(n).squareRoot())
    var factors: [Int] = []
    factors.reserveCapacity(2 * sqrtn)
    for i in 1...sqrtn {
        if n % i == 0 {
            factors.append(i)
        }
    }
    var j = factors.count - 1
    if factors[j] * factors[j] == n {
        j -= 1
    }
    while j >= 0 {
        factors.append(n / factors[j])
        j -= 1
    }
    return factors
}

Remarks:

• reserveCapacity is used to avoid array reallocations.
• All factors in the range 1...sqrtn are determined first,
  then the corresponding factors n/i are appended in reverse order,
  so that all factors are in increasing order.
• Special care must be taken that for perfect squares, sqrt(n) is
  not listed twice.

For numbers with up to 8 decimal digits, at most 9,999 trial
divisions are needed. Example
(on a 1.2 GHz Intel Core m5 MacBook, compiled in Release mode):

let start = Date()
let f = factors(of: 99999999)
print("Time:", Date().timeIntervalSince(start) * 1000, "ms")
print("Factors:", f)

Output:

Time: 0.227034091949463 ms
Factors: [1, 3, 9, 11, 33, 73, 99, 101, 137, 219, 303, 411, 657, 803, 909, 1111, 1233, 1507, 2409, 3333, 4521, 7227, 7373, 9999, 10001, 13563, 13837, 22119, 30003, 41511, 66357, 81103, 90009, 110011, 124533, 152207, 243309, 330033, 456621, 729927, 990099, 1010101, 1369863, 3030303, 9090909, 11111111, 33333333, 99999999]

Efficiently getting all divisors of a given number

Factors are paired. 1 and 24, 2 and 12, 3 and 8, 4 and 6.

An improvement of your algorithm could be to iterate to the square root of num instead of all the way to num, and then calculate the paired factors using num / i.

displaying the factors of a number

        public List<int> Divisors(int fact)
    {
        List<int> factors = new List<int>();
        int number = int.Parse(textBox2.Text);
        int factorCount = 0;
        int sqrt = (int)Math.Ceiling(Math.Sqrt(number));

        for (int i = 1; i < sqrt; i++)
        {
            if (number % i == 0)
            {
                factors.Add(i);
                factorCount += 2; //  We found a pair of factors.
            }
        }

        // Check if our number is an exact square.
        if (sqrt * sqrt == number)
        {
            factorCount++;
        }

        // return factorCount;
        return factors;
    }
    private void ShowallButton_Click(object sender, EventArgs e)
    {
        int input = int.Parse(textBox2.Text);
        List<int> factors = Divisors(input);
        string message = $"The Divisors are {string.Join(",", factors)}";
        MessageBox.Show(message);
    }

What is an efficient algorithm to find all the factors of an integer?

I'm not going to address what the best algorithm to find all factors of an integer is. Instead I would like to comment on your current method.

There are thee conditional tests cases to consider

1. (divider * divider) <= number
2. divider <= number/divider
3. divider <= sqrt(number)

See Conditional tests in primality by trial division for more detials.

The case to use depends on your goals and hardware.

The advantage of case 1 is that it does not require a division. However, it can overflow when divider*divider is larger than the largest integer. Case two does not have the overflow problem but it requires a division. For case3 the sqrt only needs to be calculated once but it requires that the sqrt function get perfect squares correct.

But there is something else to consider many instruction sets, including the x86 instruction set, return the remainder as well when doing a division. Since you're already doing number % divider this means that you get it for free when doing number / divider.

Therefore, case 1 is only useful on system where the division and remainder are not calculated in one instruction and you're not worried about overflow.

Between case 2 and case3 I think the main issue is again the instruction set. Choose case 2 if the sqrt is too slow compared to case2 or if your sqrt function does not calculate perfect squares correctly. Choose case 3 if the instruction set does not calculate the divisor and remainder in one instruction.

For the x86 instruction set case 1, case 2 and case 3 should give essentially equal performance. So there should be no reason to use case 1 (however see a subtle point below) . The C standard library guarantees that the sqrt of perfect squares are done correctly. So there is no disadvantage to case 3 either.

But there is one subtle point about case 2. I have found that some compilers don't recognize that the division and remainder are calculated together. For example in the following code

for(divider = 2; divider <= number/divider; divider++)
    if(number % divider == 0)

GCC generates two division instruction even though only one is necessary. One way to fix this is to keep the division and reminder close like this

divider = 2, q = number/divider, r = number%divider
for(; divider <= q; divider++, q = number/divider, r = number%divider)
    if(r == 0)

In this case GCC produces only one division instruction and case1, case 2 and case 3 have the same performance. But this code is a bit less readable than

int cut = sqrt(number);
for(divider = 2; divider <= cut; divider++)
    if(number % divider == 0)

so I think overall case 3 is the best choice at least with the x86 instruction set.

All factors of a given number

In Ruby, the prime library gives you the factorization:

require 'prime'
4800.prime_division #=> [[2, 6], [3, 1], [5, 2]]

To get that list of yours, you take the cartesian product of the possible powers:

require 'prime'
def factors_of(number)
  primes, powers = number.prime_division.transpose
  exponents = powers.map{|i| (0..i).to_a}
  divisors = exponents.shift.product(*exponents).map do |powers|
    primes.zip(powers).map{|prime, power| prime ** power}.inject(:*)
  end
  divisors.sort.map{|div| [div, number / div]}
end

p factors_of(4800) # => [[1, 4800], [2, 2400], ..., [4800, 1]]

Note: In Ruby 1.8.7, you must require 'mathn' instead of require 'prime'. In Ruby 1.8.6, require 'backports/1.8.7/enumerable/inject' or modify the inject above...

---

Related Topics