Best way to find all factors of a given number

Question

All numbers that divide evenly into x.

I put in 4 it returns: 4, 2, 1

edit: I know it sounds homeworky. I'm writing a little app to populate some product tables with semi random test data. Two of the properties are ItemMaximum and Item Multiplier. I need to make sure that the multiplier does not create an illogical situation where buying 1 more item would put the order over the maximum allowed. Thus the factors will give a list of valid values for my test data.

edit++: This is what I went with after all the help from everyone. Thanks again!

edit#: I wrote 3 different versions to see which I liked better and tested them against factoring small numbers and very large numbers. I'll paste the results.

static IEnumerable<int> GetFactors2(int n)
{
    return from a in Enumerable.Range(1, n)
                  where n % a == 0
                  select a;                      
}

private IEnumerable<int> GetFactors3(int x)
{            
    for (int factor = 1; factor * factor <= x; factor++)
    {
        if (x % factor == 0)
        {
            yield return factor;
            if (factor * factor != x)
                yield return x / factor;
        }
    }
}

private IEnumerable<int> GetFactors1(int x)
{
    int max = (int)Math.Ceiling(Math.Sqrt(x));
    for (int factor = 1; factor < max; factor++)
    {
        if(x % factor == 0)
        {
            yield return factor;
            if(factor != max)
                yield return x / factor;
        }
    }
}

In ticks. When factoring the number 20, 5 times each:

• GetFactors1-5,445,881
• GetFactors2-4,308,234
• GetFactors3-2,913,659

When factoring the number 20000, 5 times each:

• GetFactors1-5,644,457
• GetFactors2-12,117,938
• GetFactors3-3,108,182

Drubbing

You do know, I hope, that there isn't a general high-performance solution known to his problem. Modern cryptography relies on there being no such solution. – Braley

Yes, but I wasn't sure if there was a better way of doing it than simply testing the numbers one by one, it's been awhile since I sat through a math class. – Drubbing

related question in python – Schwing

a simple winform app which can be helpful findingnumberfactors.codeplex.com – Withal

Answer 1

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.

Kendy

One extra check to add - the above will add 2 twice :) – Disgrace

Math.Sqrt returns a double. Also, that needs to be rounded up. Try using 20 as an example. – Drubbing

Rather than taking the square root, you can restructure the loop: for(int factor = 1; factor*factor <= number; ++factor) – Ankus

True - and I would imagine there is a point past which performance would degrade for that, since you are calculating it on each loop? It is probably not as significant as other parts of the loop. Benchmarking would have to be performed, I suppose. – Kendy

cool idea Mark. you have to test against factor * factor != x when you're yielding tho. – Drubbing

This is incorrect. Take 6 as an example - max would be 2. 1, 6, 2... but not 3! You need to check from 1 until the actual square root and only add number/factor if factor is not the actual, non rounded down square root. – Wheedle

@Jake, 19 will be found when the loop gets to 2 – Kendy

Answer 2

The % (remainder) operator is the one to use here. If x % y == 0 then x is divisible by y. (Assuming 0 < y <= x)

I'd personally implement this as a method returning an IEnumerable<int> using an iterator block.

Disgrace

% is actually the modulus operator , not "remainder". The IEnumerable<int> block has an upper limit which makes this practical for factoring 'small' (computational) numbers. – Hectic

@SamuelJackson: The C# 5 language specification section 5.8.3 and Eric Lippert's blog post disagree. Your MSDN reference is to JScript, not C#. – Disgrace

@SamuelJackson: (And given that that MSDN page talks about "The modulus, or remainder, operator", it looks a little broken anyway, as if it thinks the two are equivalent...) – Disgrace

See C# Operators - under section Multiplicative Operators it is named "modulus" and under Assignment and Lambda Operators, it states "modulus assignment. Divide the value of x by the value of y, store the remainder in x, and return the new value." While modulus calculation is technically what remains after all possible divisions of the divisor, the correct mathematics term for this operation (and in c# documentation) is modulus, some refer to it as modulo. :) – Hectic

While the term "remainder" can be used, the operator is "modulus" and the result of the calculation is the remainder after all divisions are complete as a whole number. Minor technicality, but it is not uncommon (as you can see from some of Micrososft's documentation) for even those skilled to confuse the terminology between the result of this calculation, and the operator itself.. – Hectic

@Samuel: That guide you referred to is not the specification. The specification is the definitive word on this, I'd say. You can choose to ignore that if you want, but I'll use it as my choice of reference any day. I certainly won't be changing my post. – Disgrace

C# Specification 5.0 page 469 "The complete set of binary operator function names used is as follows: op_Addition, op_Subtraction, op_Multiply, op_Division, op_Modulus, op_BitwiseAnd, op_BitwiseOr, op_ExclusiveOr, op_LeftShift, op_RightShift, op_Equality, op_Inequality, op_LessThan, op_LessThanOrEqual, op_GreaterThan, and op_GreaterThanOrEqual" - also, C# Language Specification links to C# Reference - i linked prior – Hectic

@SamuelJackson: Yes, that's the name given in IL - something C# has no control over. (It's an interop matter.) Note that that's the only occurrence of the word "modulus" in the specification, whereas it consistently uses the word "remainder" for the operator, including in the section title. Nowhere in the specification does it call it the modulus operator. And while the download page for the spec does indeed refer to the C# reference guide, the spec itself does not. As far as I'm aware, the C# reference is not maintained by the language designers, who have the ultimate say in this. – Disgrace

Answer 3

Very late but the accepted answer (a while back) didn't not give the correct results.

Thanks to Merlyn, I got now got the reason for the square as a 'max' below the corrected sample. althought the answer from Echostorm seems more complete.

public static IEnumerable<uint> GetFactors(uint x)
{
    for (uint i = 1; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            yield return i;
            if (i != x / i)
                yield return x / i;
        }
    }
}

Roadrunner

Need to add the following after the for loop to return x itself. A number is always a factor of itself. yield return x; – Transference

I think whatever might have been wrong before is correct now. The reason it stops at the square root is because it already has gone through the possible factors below the square root (would be required in order to multiple by any numbers above "max"), as well as any numbers above the square root (since it outputs both itself and the number it is multiplied by to get the result). The maximum possible value that wouldn't be output yet when outputting both sides of the pair in each loop iteration is the square root. – Boccie

For example, if you get the factors of 81, then loop iterations between 10 and 40 are wasted. You've already output 27 when you output 3, and if you didn't output both sides, you would never get 81 as a factor if you stopped at 81/2 (40). – Boccie

Cheers! indeed it makes sense now. – Roadrunner

I would cache x / i instead of calculating it twice – Stlouis

Answer 4

As extension methods:

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        return from potentialFactor in Enumerable.Range(1, i)
               where potentialFactor.Divides(i)
               select potentialFactor;
    }

Here's an example of usage:

        foreach (int i in 4.Factors())
        {
            Console.WriteLine(i);
        }

Note that I have optimized for clarity, not for performance. For large values of i this algorithm can take a long time.

Aldoaldol

Answer 5

Another LINQ style and tying to keep the O(sqrt(n)) complexity

        static IEnumerable<int> GetFactors(int n)
        {
            Debug.Assert(n >= 1);
            var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1)))
                    where n % i == 0
                    select new { A = i, B = n / i };

            foreach(var pair in pairList)
            {
                yield return pair.A;
                yield return pair.B;
            }


        }

Handfast

Answer 6

Here it is again, only counting to the square root, as others mentioned. I suppose that people are attracted to that idea if you're hoping to improve performance. I'd rather write elegant code first, and optimize for performance later, after testing my software.

Still, for reference, here it is:

    public static bool Divides(this int potentialFactor, int i)
    {
        return i % potentialFactor == 0;
    }

    public static IEnumerable<int> Factors(this int i)
    {
        foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i))
                               where potentialFactor.Divides(i)
                               select potentialFactor)
        {
            yield return result;
            if (i / result != result)
            {
                yield return i / result;
            }
        }
    }

Not only is the result considerably less readable, but the factors come out of order this way, too.

Aldoaldol

Because they are two different answers, with differing merit. – Aldoaldol

Answer 7

I did it the lazy way. I don't know much, but I've been told that simplicity can sometimes imply elegance. This is one possible way to do it:

    public static IEnumerable<int> GetDivisors(int number)
    {
        var searched = Enumerable.Range(1, number)
             .Where((x) =>  number % x == 0)
             .Select(x => number / x);

        foreach (var s in searched)          
            yield return s;
    }

EDIT: As Kraang Prime pointed out, this function cannot exceed the limit of an integer and is (admittedly) not the most efficient way to handle this problem.

Kwon

This can only process for factors up to the limit of integer. – Hectic

@spencer Just curious as to why you are using yield return in a foreach loop as you already have an IEnumerable<int> why not just return the result of you Linq query instead of assigning it to searched? – Ezaria

Answer 8

Wouldn't it also make sense to start at 2 and head towards an upper limit value that's continuously being recalculated based on the number you've just checked? See N/i (where N is the Number you're trying to find the factor of and i is the current number to check...) Ideally, instead of mod, you would use a divide function that returns N/i as well as any remainder it might have. That way you're performing one divide operation to recreate your upper bound as well as the remainder you'll check for even division.

Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx

Felicific

Answer 9

If you use doubles, the following works: use a for loop iterating from 1 up to the number you want to factor. In each iteration, divide the number to be factored by i. If (number / i) % 1 == 0, then i is a factor, as is the quotient of number / i. Put one or both of these in a list, and you have all of the factors.

Entomo

Answer 10

And one more solution. Not sure if it has any advantages other than being readable..:

List<int> GetFactors(int n)
{
    var f = new List<int>() { 1 };  // adding trivial factor, optional
    int m = n;
    int i = 2;
    while (m > 1)
    {
        if (m % i == 0)
        {
            f.Add(i);
            m /= i;
        }
        else i++;
    }
    // f.Add(n);   // adding trivial factor, optional
    return f;
}

Hammering

I'd recommend providing more descriptive variable names to further enhance the readability. – Mustache

Something doesnt look right with this one. For example, the factors of 42 should return a list of 8 values. 1,2,3,6,7,14,21 and 42... But for me, this function just returns 1,2,3 and 7. Just wanted to let you know. – Thief

Answer 11

I came here just looking for a solution to this problem for myself. After examining the previous replies I figured it would be fair to toss out an answer of my own even if I might be a bit late to the party. The maximum number of factors of a number will be no more than one half of that number.There is no need to deal with floating point values or transcendent operations like a square root. Additionally finding one factor of a number automatically finds another. Just find one and you can return both by just dividing the original number by the found one.

I doubt I'll need to use checks for my own implementation but I'm including them just for completeness (at least partially).

public static IEnumerable<int>Factors(int Num)
{
  int ToFactor = Num;

  if(ToFactor == 0)
  { // Zero has only itself and one as factors but this can't be discovered through division
    // obviously. 
     yield return 0;
     return 1;
  }
    
  if(ToFactor < 0)
  {// Negative numbers are simply being treated here as just adding -1 to the list of possible 
   // factors. In practice it can be argued that the factors of a number can be both positive 
   // and negative, i.e. 4 factors into the following pairings of factors:
   // (-4, -1), (-2, -2), (1, 4), (2, 2) but normally when you factor numbers you are only 
   // asking for the positive factors. By adding a -1 to the list it allows flagging the
   // series as originating with a negative value and the implementer can use that
   // information as needed.
    ToFactor = -ToFactor;
    
    yield return -1;
   }
    
  int FactorLimit = ToFactor / 2; // A good compiler may do this optimization already.
                                  // It's here just in case;
    
  for(int PossibleFactor = 1; PossibleFactor <= FactorLimit; PossibleFactor++)
  {
    if(ToFactor % PossibleFactor == 0)
    {
      yield return PossibleFactor;
      yield return ToFactor / PossibleFactor;
    }
  }
}

Ballroom

Answer 12

Program to get prime factors of whole numbers in javascript code.

function getFactors(num1){
    var factors = [];
    var divider = 2;
    while(num1 != 1){
        if(num1 % divider == 0){
            num1 = num1 / divider;
            factors.push(divider);
        }
        else{
            divider++;
        }
    }
    console.log(factors);
    return factors;
}

getFactors(20);

Cofield

Answer 13

In fact we don't have to check for factors not to be square root in each iteration from the accepted answer proposed by chris fixed by Jon, which could slow down the method when the integer is large by adding an unnecessary Boolean check and a division. Just keep the max as double (don't cast it to an int) and change to loop to be exclusive not inclusive.

    private static List<int> Factor(int number)
    {
        var factors = new List<int>();
        var max = Math.Sqrt(number);  // (store in double not an int) - Round down
        if (max % 1 == 0)
            factors.Add((int)max);

        for (int factor = 1; factor < max; ++factor) //  (Exclusice) - 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 need check anymore) - Don't add the square root twice!  Thanks Jon
                factors.Add(number / factor);
            }
        }
        return factors;
    }

Usage

Factor(16)
// 4 1 16 2 8
Factor(20)
//1 20 2 10 4 5

And this is the extension version of the method for int type:

public static class IntExtensions
{
    public static IEnumerable<int> Factors(this int value)
    {
        // Return 2 obvious factors
        yield return 1;
        yield return value;
        
        // Return square root if number is prefect square
        var max = Math.Sqrt(value);
        if (max % 1 == 0)
            yield return (int)max;

        // Return rest of the factors
        for (int i = 2; i < max; i++)
        {
            if (value % i == 0)
            {
                yield return i;
                yield return value / i;
            }
        }
    }
}

Usage

16.Factors()
// 4 1 16 2 8
20.Factors()
//1 20 2 10 4 5

Kyliekylila

Answer 14

There is a premade class for that "NumberProperties". NumberPropertiesController.Calculate_FactorInfo(ref props) calculates the factors. NumberProperties.FactorLists gives you the factors.

I am not sure though, in which .Net Framework it is in. Anyone got a link?

Huttan

Answer 15

Linq solution:

IEnumerable<int> GetFactors(int n)
{
  Debug.Assert(n >= 1);
  return from i in Enumerable.Range(1, n)
         where n % i == 0
         select i;
}

Yip

This only gets you the first 1/2 of factors. e.g., for 10, it would return 1 and 2, but not 5 and 10. – Aldoaldol

Suggested change: Math.Sqrt will return a double, which won't work with Enumerable.Range. Also that won't return 4 - just 1 and 2. – Disgrace