Prime Factoring using a Visual Basic Module

prime factoring logo
msofficeshare logo

Requirement:  Visual Basic Knowledge

File to download:  Factoring.xlsm

A prime number (or just “prime”) is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number.  Theoretically, the number of primes should be infinite.

Primes are utmost importance to number theorists because they are the building blocks of whole numbers.  They are the basis of multiples and arithmetic.  In everyday life, prime numbers are critical in many applications.  A lot of algorithms develop in number theory for communication security (aka cryptography) and for transmission and compression of information. They depend on number theory and ultimately on prime numbers.  In addition, primes have applications to architecture, acoustic design, signal processing, music theory, quantum mechanics and physics.  Primes are so pervasive in our lives that it is almost impossible to think of any aspect of our lives that is not affected by them.

Doing prime factorization by using hand calculations or calculators has never been easy.  I still vividly remember the painful experience that I was forced to memorize the prime numbers in the elementry school.  So I would like to present you this rudimentary prime factoring visual basic (VB) module and hope that it will make your life (or our kids’ lives) a bit easier.  The VB module I created is scalable.  It now only stores the first 100 prime numbers but you can extend them to as many as you want.  The limit is the speed of your computer and the time you can put in to wait for the running result.  In addition, my VB module only takes one number at a time.  But you can add another loop to feed the data in one-by-one or make the input data as an array.

pic1 prime factoring

 

The left illustration shows the interface of the program.  It is relatively simple.  The user puts in a whole number (without decimal places) in cell B3 and click the “Go !” button.  The VB module will go through 2 loops to generate the list of the prime factors.  The result will be listed starting from cell B5.  If there is no prime number for the calculation, the input number will show up as the prime factor.  Please remember that this program only stores the first 100 prime numbers (which are stored on the “Prime” worksheet).  If the factoring requires prime numbers that exceed the first 100 ones, the result will be erred.

Below are the visual basic codes for the module.  There are 2 loopings in the VB module.  The first looping (FOR loop) loops through the first 100 prime numbers one-by-one to see if one of the prime numbers can divide the input number.  However, the FOR loop will be prematurely terminated once the input number is factored to 1. 

The second looping (DO loop) will use the same prime number and keep on dividing the input number.  For example, the factors of an input number (e.g. 1,500) are 2 * 2 * 3 * 5 * 5 * 5.  You can see the same prime numbers (2 and 5) appear more than once.  The DO loop is doing such repetition until the factoring by the same prime numbers is no longer valid.

Sub Factoring()

    Dim prime(1 To 100) As Integer, i As Integer

    Dim InputNbr As Long

   

    Sheets("Prime").Select

    Range("A3").Select

    For i = 1 To 100        'Read first 100 prime numbers into the array

        prime(i) = ActiveCell.Value

        ActiveCell.Offset(1, 0).Select

    Next i

   

    Sheets("Factoring").Select

    InputNbr = Range("InputNbr").Value

    Range("B5:B1000").Select

    Selection.ClearContents

   

    Range("B5").Select

   

    For i = 1 To 100

        If InputNbr = 1 Then

            Exit For

        End If

 

        Do While InputNbr Mod prime(i) = 0      'check remainder, if 0, the InputNbr can be factored

            InputNbr = InputNbr / prime(i)

           

            ActiveCell.Value = prime(i)         'write the factoring result

            ActiveCell.Offset(1, 0).Select

        Loop

    Next i

   

    If InputNbr > 1 Then        'write remainder

        ActiveCell.Value = InputNbr

    End If

End Sub