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

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 …

Cool, this is a nice and well written code!

Hi,

I have a question. What is that txtFactors?

Controls with names beginning with

txtare text boxes. In this example,txtFactorsis the control where the program displays the result. If you download the example program you’ll see it.Pingback: Determine whether a number is prime in C# - C# HelperC# Helper