Title: Find a number's prime factors in C#

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 * 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 the example to experiment with it and to see additional details.