THE PUZZLET PAGE


How_Does_It_Work


SUBROUTINE: PrintPrimeFactors().  This subroutine prints out all the prime factors of its argument in ascending order.

The prime factors of an integer are the prime number(s) which are its sub-multiples.  For example, the prime factors of 10 are 2 and 5; the prime factors of 24 are 2, 2, 2, 3. Obviously, the prime factor of a prime is itself.

Clearly, the subroutine is dealing with primes in two ways - checking initially as to whether the argument itself is prime, and then generating prime factors of increasing magnitude.  To perform these tasks, it has to call on the function IsPrime().  You can obtain this function from these pages.  Click here to do so now.

This version of PrimeFactors() prints the prime factors out to the screen.  There will be times when this isn't convenient, and it's easy to set up an array to store them for further manipulation later.  Altering the code is very simple.  If you need further help here, just e-mail me by following the link at the bottom of the screen.

This code will only find the prime factors of numbers up to the maximum possible value of argument p. If p is declared as an integer (int), that means 1073741824. See the table below for the limits.

Type

Exponent of 2
Value

int 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 4611686018427387904

Declaring the function must be done like this:

declare PrimeFactors(p: int)

With those constraints in mind, here's the code:

sub PrintPrimeFactors(p)
' prints all the primes factors,
' in order, of argument p.
def temp, fctr: int
if IsPrime(p): 'is its own prime factor
    print p,
else
    temp = p: 'copy argument into temp
    fctr = 2: ' lowest possible prime factor
    do:  deals with prime factor 2 only
        if temp % fctr = 0
: ' is 2 a factor?
            print fctr,
            temp = temp/fctr: 'reduce temp
        endif
    until temp % fctr <> 0: 'until 2 not a factor
    fctr = 3: 'first odd factor
    do: deals with odd prime factors only
        if temp % fctr = 0: 'is fctr a factor?
            print fctr,
            temp = temp/fctr: 'reduce temp
        else
            ' get next potential prime factor
            do
                fctr = fctr + 2: 'get next odd number
            until IsPrime(fctr)
        endif
    until temp = 1: 'temp completely reduced

endif
return

The algorithm used here is very simple, as shown in the flowchart.

FlowChart

The only even prime factor possible is 2, and that is dealt with first. Let's use a value of 60 for p to give a worked example.  60 divides by 2, so that's the first prime factor, leaving 30. 30 also divides by 2, leaving 15, so 2 is the second factor as well.

15 doesn't divide by 2, so the flowchart moves on by setting fctr to 3.  15 divides by 3, so that's the third factor, leaving 5.  5 doesn't divide by 3, so the flowchart continues to the next part of the process. It increments fctr to 5. This is acceptable for trial, as it's also a prime.

5 divides by 5, so this is the fourth factor, leaving p equal to 1. That's the exit condition, and the job's all done.

Once p equal unity, the algorithm is DONE, and quits, having yielded up prime factors of 60 correctly as 2, 2, 3, 5.

I'm going to add line numbers to the rest of the code to make the description simpler.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def temp, fctr: int
if IsPrime(p): 'is its own prime factor
    print p,
else
    temp = p: 'copy argument into temp
    fctr = 2: ' lowest possible prime factor
    do
:  deals with prime factor 2 only
        if temp % fctr = 0
: ' is 2 a factor?
            print fctr,
            temp = temp/fctr: 'reduce temp
        endif
    until temp % fctr <> 0: 'until 2 not a factor
    fctr = 3: 'first odd factor
    do:  deals with oddprime factors only
        if temp % fctr = 0: 'is fctr a factor?
            print fctr,
            temp = temp/fctr: 'reduce temp
        else
            do
                fctr = fctr + 2: 'get next odd number
            until IsPrime(fctr)
        endif
    until temp = 1: 'temp completely reduced

endif
return


Now for a line-by-line exegesis of the code.

1

def temp, fctr: inttemp is the local variable to be used to hold the initial value of argument ptemp will be manipulated until its value eventually becomes 1, while the original argument will be unchanged.  Variable fctr holds the value of the current candidate factor.

2

if IsPrime(p).  If the argument is already prime, it will only have one prime factor: itself.  In this case, all that's necessary is to print the argument and quit.  So this line asks "Is argument p prime?"  It does this by calling function IsPrime().  Obviously, that function must be included with this one, as explained above.

3

print p.  If this line is reached, it means the answer to the question in line 2 is "yes," so we can print the argument itself.  The ENDIF associated with line 2 is actually line 24, so you can see that the subroutine quits right after printing the argument.

4

else.  If the answer to line 2 is "no," the argument isn't prime, and we can get right to work on the alternative action of finding its prime factors. The  else  here indicates that what follows is the alternative action.

5

temp = p.  We will be manipulating the argument now, so it's copied into local variable temp.

6

fctr = 2.  The lowest possible prime factor of an integer is 2, since this is the lowest possible prime number.  2 is always a prime factor of even numbers.

7

do.  Opens the first DO loop.  This one is associated exclusively with the special case where fctr equals 2.  This is a special case because 2 is the only even prime number.

8

if temp % fctr = 0.  Now the work begins!  We want to know if 2 is a factor of temp.  (Remember, fctr is at this point in time loaded with value 2).  The way this check is made is to use integer arithmetic.  temp is divided by fctr, and a check made to see if there's a remainder or not.  If there's no remainder, temp must be a multiple of fctr, 2 in this case.  So the line can be paraphrased as "Does dividing temp by fctr leave a remainder?"

9

print fctr.  If this line is reached, fctr must be a prime factor of temp, so it's printed out.

10

temp = temp/fctr.  We have just found a prime factor of temp.  In order to find the next one, we have to reduce temp by the ratio of its factor.  So, If temp was 60 and fctr was 2, we divide 60 by 2, leaving 30, and this is the new value of temp to work with.  Line 10 is effectively saying "Divide  temp by fctr and save the result in variable temp, over-writing what was already in there."  This process continues until temp is eventually reduced to 1, when the process is complete.

11

endif.  Housekeeping - closes IF-ENDIF clause.

12

until temp % fctr <> 0.  We've reached the end of the first DO loop, and must decide whether to quit or not.  Let's stick with the example where temp equals 60.  We've found it divides by 2, printed out the 2, and divided temp by 2 so that temp now equals 30.  Will 30 divide by 2 as well?  If it does, execute the loop again, if not, quit - simple.  So line 12 is saying "If temp divides by 2 with no remainder, execute the DO loop again, if not quit and move on to the next section of code."

Of course, 30 does indeed divide by 2, so the loop will be executed again.  This time, another 2 is printed out (because 2 is a prime factor of 60 twice) and temp is reduced further to 15.  15 doesn't divided by 2 without remainder, so the DO loop will be quit at this point.

13

fctr = 3.  We've finished with 2 as a prime factor, and won't need to look at even numbers again (because no other even numbers are prime).  Now it's time to deal with the odd primes, and we start with the lowest possible, 3.  fctr is set to 3 in preparation.

14

do.  Opens the second DO loop, dealing with odd primes only.

15

if temp % fctr = 0. The same method is used with odd primes as with even, described above.  If temp divides exactly by fctr with no remainder, fctr must be a factor of temp.

16

print fctr.  If the answer to the question in line 16 is "yes", we can print the factor out.

17

temp = temp/fctr. Just as we reduced temp for even number factors, so we further reduce it for odd number factors.  Take the example we were following of temp having been reduced to 15.  Now, 15 divides by 3, so 3 is a prime factor and is printed out.  Then temp is divided by fctr, leaving a value of 5 to work with.


18

else.  Of course, it's possible that temp couldn't be divided by fctr as checked in line 16.  Let's take an example.  If temp  equals 13, it won't divide by 3, and alternate action will be necessary.  That's just what the else is there for.

19

do.  Opens inner DO loop.  This loop is associated exclusively with producing the next highest prime factor.

20

fctr = fctr + 2. The next prime factor must always be an odd number, and the nearest could be just two higher.  This line just increments fctr by two to get the next odd number to try out.

21

until IsPrime(fctr).  We want to keep the loop going until it finds the next prime.  Line 21 is saying "Is the newly-incremented value in fctr a prime?  If it isn't, execute the DO loop again.  If it is, quit the DO loop."  So fctr will continue to be incremented by 2 until eventually it becomes a prime number, and the loop quits.

22

endif.  Housekeeping - closes inner IF-ENDIF clause.

23

until temp = 1. The outer DO loop now comes to its last line. It will keep re-executing until it has reduced temp to 1, when the process is complete.  Line 24 can be paraphrased as "If the value in variable temp is other than 1, execute the DO loop again.  If it equals 1, quit the DO loop."

24

endif.  Housekeeping - closes outer IF-ENDIF clause.

25

return.  Job done - return program control to main routine.

Let's look at a simple example of the subroutine at work, using 117 as the argument.

temp
fctr
Output
Comments




117
2
nil
117 doesn't divide by 2.  Try 3
117
3
3
Exact division. 117/3 = 39
39
3
3
Exact division.  39/3 = 13
13
3
nil
13 doesn't divide by 3.  Try 5
13
5
nil
13 doesn't divide by 5.  Try 7
13
7
nil
13 doesn't divide by 7.  Try 11 (9 isn't prime)
13
11
nil
13 doesn't divide by 11.  Try 13
13
13
13
Exact division.  13/13 = 1
1


temp = 1.  Subroutine quits.

You can see how temp's value reduces each time there's an output.  Once it's found all the prime factors, its value is 1, which is the signal to quit.  Along the way, it printed out the prime factors 3, 3, 13 in order.

MAIN MENU
HOW DOES IT WORK?

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 5th, 2010.