by Zoran Horvat

Mar 09, 2014

Given a positive integer number, write a function which returns an array with all prime factors of that number.

Examples: If number 1064 is passed, the function should return array with numbers 2, 2, 2, 7 and 19. If number 1 is passed to the function, an array containing only value 1 should be returned.

Breaking the input number N into its prime constituents can be accomplished by attempting to divide it by different candidate values. One of the difficulties that we are facing is then to find proper candidates. First of all, they must be greater than one. If input number is equal to one, then number one alone is the only factor and the process ends. Otherwise, valid candidates will start from value 2. The upper bound for candidates would then be the greatest number not exceeding square root of N. It would be pointless to try to divide N by any number greater than its square root, because such factor would already have been found earlier. For detailed analysis, please refer to exercise Finding All Prime Numbers Smaller Than Specified Value.

By this point we have established the domain from which possible prime factors are drawn. It is the set of numbers between 2 and square root of N, inclusive. The factorization process would then go like this. As we take candidates in turns, we try whether each of them divides N with no remainder. In case of success, we know that the real factor is found and it is immediately added to the resulting array.

But then, two important consequences occur. First, number N should be divided by the current factor, so that the prime factor is removed from it. (On a related note, we know that the factor is prime because all smaller values have already been tried out.) This also means that upper bound for candidates, the square root of N, reduces as well and the set of remaining candidates shrinks. Second consequence is that we do not move to the next candidate. Instead, the same candidate is retained, because it might divide N more than once.

Finally, after all candidates have been exhausted, number N will still be greater than one. That value would be the final prime factor, the one that could not be split into smaller factors using division.

So this is the algorithm. Before putting it in motion, we can make one additional observation. Apart from numbers 2 and 3, no other value divisible by 2 or 3 should be taken as candidate. Such numbers are obviously not prime and cannot be promoted to the output. This means that only numbers in form 2k-1 and 2k+1 remain, for any positive k, in addition to primes 2 and 3. This simple action reduces the candidates set roughly by two thirds, improving the overall algorithm performance. (The same idea was also used in exercise Finding All Prime Numbers Smaller Than Specified Value).

Now that everything is in place, we can write the pseudocode:

```
function GetPrimeFactors(n)
-- n - positive number
begin
factors - empty array
if n = 1 then
factors = [1]
else
begin
factor = 2
step = 2
while factor * factor <= n
begin
if n mod factor = 0 then
append factor to factors
n = n / factor
else if factor < 3 then
factor = factor + 1
else if factor < 5 then
factor = factor + 2
else
factor = factor + step
step = 6 - step
end
append n to factors
end
return factors
end
```

Below is the console application in C# which lets the user enter number N and then splits the number into its prime factors.

```
using System;
using System.Collections.Generic;
namespace PrimeFactorization
{
class Program
{
private static int[] GetPrimeFactors(int n)
{
List<int> factors = new List<int>();
if (n == 1)
factors.Add(1);
else
{
int factor = 2;
int step = 2;
while (factor * factor <= n)
{
if (n % factor == 0)
{
factors.Add(factor);
n = factor;
}
else if (factor < 3)
{
factor++;
}
else if (factor < 5)
{
factor += 2;
}
else
{
factor += step;
step = 6 - step;
}
}
factors.Add(n);
}
return factors.ToArray();
}
static void Main()
{
while (true)
{
Console.Write("Enter positive number (zero to exit): ");
int n = int.Parse(Console.ReadLine());
if (n <= 0)
break;
int[] factors = GetPrimeFactors(n);
PrintFactors(n, factors);
}
}
private static void PrintFactors(int n, int[] factors)
{
Console.Write("{0} = {1}", n, factors[0]);
for (int i = 1; i < factors.Length; i++)
Console.Write(" * {0}", factors[i]);
Console.WriteLine();
Console.WriteLine();
}
}
}
```

When application above is run, it produces the following output:

```
Enter positive number (zero to exit): 1064
1064 = 2 * 2 * 2 * 7 * 19
Enter positive number (zero to exit): 574
574 = 2 * 7 * 41
Enter positive number (zero to exit): 912
912 = 2 * 2 * 2 * 2 * 3 * 19
Enter positive number (zero to exit): 9954
9954 = 2 * 3 * 3 * 7 * 79
Enter positive number (zero to exit): 0
```

- Next: Finding Numbers Which Appear Once in an Unsorted Array
- Previous: Finding a Number which Appears Once in Array where All Other Numbers Appear Three Times
- Finding All Prime Numbers Smaller Than Specified Value
- LINQ Expression to Test If a Number is Prime
- LINQ Expression to Find All Prime Numbers

If you wish to learn more, please watch my latest video courses

This course begins with examination of a realistic application, which is poorly factored and doesn't incorporate design patterns. It is nearly impossible to maintain and develop this application further, due to its poor structure and design.

As demonstration after demonstration will unfold, we will refactor this entire application, fitting many design patterns into place almost without effort. By the end of the course, you will know how code refactoring and design patterns can operate together, and help each other create great design.

More...

In four and a half hours of this course, you will learn how to control design of classes, design of complex algorithms, and how to recognize and implement data structures.

After completing this course, you will know how to develop a large and complex domain model, which you will be able to maintain and extend further. And, not to forget, the model you develop in this way will be correct and free of bugs.

More...

Zoran Horvat is the Principal Consultant at Coding Helmet, speaker and author of 100+ articles, and independent trainer on .NET technology stack. He can often be found speaking at conferences and user groups, promoting object-oriented development style and clean coding practices and techniques that improve longevity of complex business applications.

- Overcoming the Limitations of Constructors
- Does the Command Pattern Require Undo?
- What Makes while Loop a Poor Choice in Programming
- How to Wrap System.Random Into an Infinite IEnumerable<int> Sequence
- Substituting the Builder with the Sequence of Factory Methods
- Custom Implementation of the Option/Maybe Type in C#
- More...

- Making Your C# Code More Object-oriented
- Making Your C# Code More Functional
- Writing Purely Functional Code in C#
- Tactical Design Patterns in .NET: Creating Objects
- Tactical Design Patterns in .NET: Control Flow
- Tactical Design Patterns in .NET: Managing Responsibilities
- Advanced Defensive Programming Techniques
- Writing Highly Maintainable Unit Tests
- Improving Testability Through Design