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 submultiples. 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 email 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  2^{30}  1073741824 
uint  2^{31}  2147483648 
int64  2^{61}  2305843009213693952 
uint64  2^{62}  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. 
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 linebyline exegesis of the code. 
1 
def temp, fctr: int. temp is the local variable to be used to hold the initial value of argument p. temp 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, overwriting what was already in there." This process continues until temp is eventually reduced to 1, when the process is complete. 
11 
endif. Housekeeping  closes IFENDIF 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 newlyincremented 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 IFENDIF clause. 
23 
until temp = 1. The outer DO loop now comes to its last line. It will keep reexecuting 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 IFENDIF 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 Email me!
Last Updated: February 5th, 2010.