Find a number’s prime factors in C#

example

Once upon a time, I read an article where the author said something like this:

My professor asked us whether we had prime factored our Social Security numbers yet. Being a normal person, I laughed with everyone else. Being a nerd, I managed to resist for only three days.

Of course I immediately rushed to my computer and wrote a prime factoring program. At the time it was kind of hard because the computer I was using didn’t have integers big enough to hold Social Security numbers. This is a lot easier now.

This example uses the following FindFactors method to find a number’s prime factors.

// Return the number's prime factors.
private List FindFactors(long num)
{
    List result = new List();

    // Take out the 2s.
    while (num % 2 == 0)
    {
        result.Add(2);
        num /= 2;
    }

    // Take out other primes.
    long factor = 3;
    while (factor * factor <= num)
    {
        if (num % factor == 0)
        {
            // This is a factor.
            result.Add(factor);
            num /= factor;
        }
        else
        {
            // Go to the next odd number.
            factor += 2;
        }
    }

    // If num is not 1, then whatever is left is prime.
    if (num > 1) result.Add(num);

    return result;
}

First, while the number num is divisible by 2, the program adds 2 to the list of factors and divides num by 2.

Next, for odd numbered values factor = 3, 5, 7, and so on, the program determines whether factor divides evenly into num. If factor does divide evenly into num, the program adds factor to the list of factors and divides num by it. If factor does not divide num evenly, the program adds 2 to factor to check the next odd number.

The program stops when factor &mult; factor is greater than num.

The following code shows how the program uses this method.

// Get the number's factors.
long num = long.Parse(txtNumber.Text);
List<long> factors = FindFactors(num);

// Display the factors.
List<string> strings = factors.ConvertAll(x => x.ToString());
txtFactors.Text = string.Join(" x ", strings.ToArray());

This code first calls the FindFactors method to get the list of factors.

That list contains long integers and the program needs strings, so the code calls the list’s ConvertAll method. That’s a LINQ extension method that takes as a parameter a method that converts each of the items in the list into a new type. This example uses the lambda expression x => x.ToString() to call each value’s ToString method to convert it into a string.

Finally the code calls the string.Join method to merge the factors (now strings) into a single string. It uses the list’s ToArray LINQ extension method to convert the list into an array because string.Join cannot work with a list. The code finishes by displaying the concatenated results in its text box.


Download Example   Follow me on Twitter   RSS feed




This entry was posted in algorithms, mathematics and tagged , , , , , , , , , , , . Bookmark the permalink.

4 Responses to Find a number’s prime factors in C#

  1. Probabilistically determine whether a number is prime in C#

    This is a cool little algorithm that uses some clever mathematics. This algorithm and several related algorithms are described in my book Essential Algorithms: A Practical Approach to Computer Algorithms. I think it’s a really good book (and it’s gotten very good reviews) so if you’re interested in this sort of thing (or other algorithms), check it out! The example also demonstrates a crucial technique in C# programming when you’re performing integer arithmetic. Before I describe the program, you should know a bit about why it’s important to decide whether a number …

  2. mathnerd says:

    Cool, this is a nice and well written code!

  3. loushing says:

    Hi,
    I have a question. What is that txtFactors?

    • RodStephens says:

      Controls with names beginning with txt are text boxes. In this example, txtFactors is the control where the program displays the result. If you download the example program you’ll see it.

Leave a Reply

Your email address will not be published. Required fields are marked *