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]

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...

Generating all factors of a number given its prime factorization

Imagine prime divisors are balls in a bucket. If, for example, prime divisors of your number are 2, 2, 2, 3 and 7, then you can take 0, 1, 2 or 3 instances of 'ball 2'. Similarly, you can take 'ball 3' 0 or 1 times and 'ball 7' 0 or 1 times.

Now, if you take 'ball 2' twice and 'ball 7' once, you get divisor 2*2*7 = 28. Similarly, if you take no balls, you get divisor 1 and if you take all balls you get divisor 2*2*2*3*7 which equals to number itself.

And at last, to get all possible combinations of balls you can take from the bucket, you could easily use recursion.

void findFactors(int[] primeDivisors, int[] multiplicity, int currentDivisor, long currentResult) {
    if (currentDivisor == primeDivisors.length) {
        // no more balls
        System.out.println(currentResult);
        return;
    }
    // how many times will we take current divisor?
    // we have to try all options
    for (int i = 0; i <= multiplicity[currentDivisor]; ++i) {
        findFactors(primeDivisors, multiplicity, currentDivisor + 1, currentResult);
        currentResult *= primeDivisors[currentDivisor];
    }
}

Now you can run it on above example:

findFactors(new int[] {2, 3, 7}, new int[] {3, 1, 1}, 0, 1);

I have a Python list of the prime factors of a number. How do I (pythonically) find all the factors?

Instead of a list of exponents, consider simply repeating each prime factor by the number of times it is a factor. After that, working on the resulting primefactors list-with-repetitions, itertools.combinations does just what you need -- you'll just require the combinations of length 2 to len(primefactors) - 1 items included (the combinations of just one are the prime factors, that of all of them will be the original number -- if you want those too, just use range(1, len(primefactors) + 1) instead of the range(2, len(primefactors)) which my main suggestion would use).

There will be repetitions in the results (e.g., 6 will appear twice as a factor of 12, since the latter's primefactors will be [2, 2, 3]) and they can of course be weeded out in the usual ways (i.e. sorted(set(results)) for example).

To compute primefactors given listOfAllPrimes, consider for example:

def getprimefactors(n):
    primefactors = []
    primeind = 0
    p = listOfAllPrimes[primeind]
    while p <= n:
        if n % p == 0:
            primefactors.append(p)
            n //= p
        else:
            primeind += 1
            p = listOfAllPrimes[primeind]
    return primefactors

How to find all factors of a number for a given number range

You can achieve same thing without checking for every number between numbers[0] & numbers[1]. What you need basically is to get every multiple of factor between numbers[0] & numbers[1]. Below code does it:

function getFactors(factor, numbers) {
  let factors = new Array();
  let start = numbers[0]/factor;
  let end = numbers[1]/factor;
  for(var i=start; i<= end; i++) {
    factors.push(factor*i);
  }

  return factors
}
console.log(getFactors(5,[50,100]))
//[50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]

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

(divider * divider) <= number
divider <= number/divider
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.

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);
    }