http://www.codinghelmet.com/  

Wear a helmet. Even when coding.

exercises > prime-factorization

Exercise #26: Prime Factorization
by Zoran Horvat @zoranh75

Problem Statement

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.

Problem Analysis

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

Implementation

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();
        }

    }

}

Demonstration

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

See also:

Published: Mar 9, 2014; Modified: Dec 14, 2014

ZORAN HORVAT

Zoran is software architect dedicated to clean design and CTO in a growing software company. Since 2014 Zoran is an author at Pluralsight where he is preparing a series of courses on object-oriented and functional design, design patterns, writing unit and integration tests and applying methods to improve code design and long-term maintainability.

Follow him on Twitter @zoranh75 to receive updates and links to new articles.

Watch Zoran's video courses at pluralsight.com (requires registration):

Making Your C# Code More Object-Oriented

This course will help leverage your conceptual understanding to produce proper object-oriented code, where objects will completely replace procedural code for the sake of flexibility and maintainability. More...

Advanced Defensive Programming Techniques

This course will lead you step by step through the process of developing defensive design practices, which can substitute common defensive coding, for the better of software design and implementation. More...

Tactical Design Patterns in .NET: Creating Objects

This course sheds light on issues that arise when implementing creational design patterns and then provides practical solutions that will make our code easier to write and more stable when running. More...

Tactical Design Patterns in .NET: Managing Responsibilities

Applying a design pattern to a real-world problem is not as straight-forward as literature implicitly tells us. It is a more engaged process. This course gives an insight to tactical decisions we need to make when applying design patterns that have to do with separating and implementing class responsibilities. More...

Tactical Design Patterns in .NET: Control Flow

Improve your skills in writing simpler and safer code by applying coding practices and design patterns that are affecting control flow. More...

Writing Highly Maintainable Unit Tests

This course will teach you how to develop maintainable and sustainable tests as your production code grows and develops. More...

Improving Testability Through Design

This course tackles the issues of designing a complex application so that it can be covered with high quality tests. More...

Share this article

webmasters