FUNCTION:
CountPrimeFactors(). Pass an integer to this function
and it will generate all its prime factors, count them, and return
the count to the calling routine. Note that this function uses two other functions: GetNextPrime() and IsPrime() Obviously, you must include both these functions with CountPrimeFactors() for the latter to work. To obtain copies, go to How Does It Work? now. It's up to you what data type you make the argument, depending on the type of integer you want to process. 
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 CountPrimeFactors(p: int) (or whatever integer type you want). Here's the code: sub CountPrimeFactors(p) ' counts all the primes factors of ' argument p and returns the count ' to the calling routine. ' By Dave Ellis. def count, temp, fctr: int if IsPrime(p): 'is its own prime factor count = 1 else count = 0 temp = p: 'copy argument into temp do: 'deals with prime factor 2 only if temp % 2 = 0: 'is 2 a factor? count = count + 1 temp = temp/2: 'reduce temp endif until temp % 2 <> 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? count = count + 1 temp = temp/fctr: 'reduce temp else ' get next potential prime factor fctr = GetNextPrime(fctr) endif until (temp = 1)  (fctr > temp): 'all done endif return count OVERVIEW AND STRATEGY. 
A
flowchart is shown inset to help illustrate how the function works. As soon as the function is called, it checks to see if the argument passed to, held in variable p, is itself a prime. If it is the count of prime factors, held in variable count, is set to one (since a prime number can only have one prime factor) and the code jumps to the end ready to exit. If p isn't a prime, count is set to zero. Another variable, temp, is loaded with a copy of p at this time. Now the code checks to see if p divides exactly be 2. If it does, this is a prime factor, and count is incremented. temp is then divided by 2 ready for the next check. This division by the latest prime factor keeps reducing the value stored in temp, and successive iterations will eventually reduce temp to one. At that point, all the prime factors will have been identified. 
As long as division by 2 is possible,
further divisions will be tried. For example, if p's value is 8, you'll get three
divisions, after which count
equals three and temp equals
1, the exit condition. This indicates that there are three prime
factors of 8, all of which are 2's. When no further divisions by 2 are possible, the code introduces another variable, fctr (short for factor). This is initialised to value 3. A check is made to determine if the value in temp will divide exactly by 3. If it does, another prime factor has been found. As before, count is incremented and temp is divided by fctr. If it doesn't the function GetNextPrime() is called and its returned value (the next higher prime to whatever was stored in fctr) is loaded into fctr, overwriting whatever was stored in there (on the first pass, it will be a 3). If the value of temp at this point has been reduced to unity (1), the job is complete. The flowchart shows that the code jumps to the "done" box. If it hasn't a further check is made to see if fctr is still greater than temp. If it isn't, all factors have been found, and the program quits. If it is, the code jumps back to checking whether temp divides exactly by fctr. You can get a feel for how this all works by looking at an example of what goes on with a real check. This kind of exercise is called a trace You will see that an input of 42 takes five iterations to find all three prime factors, which are 2, 3, and 7. 
iteration nr  p  temp  count  fctr 
1  42  42  0  
2  42  21  1  
3  42  7  2  3 
4  42  7  2  5 
5  42  1  3  7 
In the description of the code which
follows, I have applied line numbers to make it easier to follow.
Here
they are: 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 
def count, temp, fctr: int if IsPrime(p): 'is its own prime factor count = 1 else count = 0 temp = p: 'copy argument into temp do: 'deals with prime factor 2 only if temp % 2 = 0: 'is 2 a factor? count = count + 1 temp = temp/2: 'reduce temp endif until temp % 2 <> 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? count = count + 1 temp = temp/fctr: 'reduce temp else fctr = GetNextPrime(fctr) endif until (temp = 1)  (fctr > temp): 'all done endif return count 
Now
for a linebyline exegesis of the code. 
1

def count, temp, fctr: int. Defines the three variables
used by the code:

2 
if IsPrime(p). Passes the contents of variable p to the function IsPrime(), which will return TRUE (1) if the argument is prime, otherwise FALSE (0). Effectively, this line is asking the question "Do the contents of variable p make a prime number?" 
3 
count = 1.
This line is only executed if the answer to the question in line
two
is "Yes," which is indicated if TRUE is returned. After execution
of
line 3, the code will jump to the relevant ENDIF at line 23. 
4 
else. Indicates that alternative code exists. If the answer to the question in line 2 is "No," indicated if FALSE is returned from IsPrime(0), the code beginning on line 5 is executed next. 
5 
count = 0. Initialises the contents of variable count to zero. 
6 
temp = p. The contents of argument p are copied into variable temp. This is necessary because its value will be manipulated by the following code, and it's bad practice to manipulate the code directly if it's not necessary. It means the value is lost, which would be a disaster if it were needed later in the function. If you needed to speed up the execution, and there was no danger, you could ignore this rule of thumb. 
7 
do. Opens a DO loop. 
8 
if temp % 2 = 0. The lowest possible prime factor is 2, which is dealt with first. It is dealt with differently to the other prime factors because it is the only one which is an even number. The % sign is part of what is called integer arithmetic, and means "make a division, and discard everything but the remainder." So line 8 is effectively asking the question "Do the contents of variable temp divide exactly by 2?" And remember, temp at this time holds a copy of argument p, the number whose prime factors we wish to find and count. 
9 
count = count + 1. This line is only executed if the answer to the question posed in line 8 is "Yes." It means that the code found 2 was a factor of the number being investigated, so the value stored in variable count is incremented by 1. After execution of line 9, the code jumps to line 11. 
10 
temp = temp/2.
Execution of line 10 also requires the answer to the question in
line
8 to be "Yes." This is another integer arithmetic operation.
The
backslash means "Perform a division and discard any remainder." In this
case, the contents of variable temp
are divided by 2 and the result stored back into temp, overwriting what was
previously stored in there. 
11 
endif. Housekeeping: closes the ifendif clause opened in line 8. 
12 
until temp
% 2 <> 0.
Also housekeeping, but more complex! It closes the DO loop
opened in
line 7, but the closure isn't automatic  it's conditional. So a
decision is going to be made here as to whether to close and exit the
DO loop or to go around again to line 7. We have another integer arithmetic calculation as part of the condition. It checks to see if, after dividing the contents of variable temp by 2, there is a remainder. So the whole line can be paraphrased thus: "If the contents of variable temp can be divided exactly by 2, go around the DO loop again, if not just quit and go on to the next line of code." The
reason is simple: if this exact division is possible, another
prime
factor (2) exists to be dealt with before looking for larger prime
factors. For instance, if temp
contained 32, the DO loop would have to be executed five times before
executing, because 32 can be divided by 2 five times in succession
before it's reduced to an odd number (1).

13 
fctr = 3. This line is only executed after all possible prime factors of value 2 have been identified and counted. The divisions will have been carried out until variable temp was itself reduced to an odd number. For example, if temp started off holding 36, it would be divided by 2 to hold 18, then divided again by 2 to hold 9 before moving on to line 13. 
14 
do. Opens a second DO loop. 
15 
if
temp % fctr = 0. Instead of dividing directly by
2 as above, we are now dividing by the contents of variable fctr, which
was initialised in line 13 to value 3. Othewise this line
operates exactly as does line 8. 
16 
count = count + 1. Identical in operation to line 9, except we are reacting here to the contents of variable fctr rather than the number 2. 
17 
temp = temp/fctr. Once again, identical in operation to line 10, except we are reacting here to the contents of variable fctr rather than the number 2. 
18 
else. Indicates alternative action if
the answer to the question in line 15 in "No." Line 18 isn't
executed if the answer was "Yes." 
19 
fctr = GetNextPrime(fctr). This is the alternate action to lines 16 and 17. Whatever value is stored in variable fctr is passed as parameter to the function GetNextPrime(), which will return the next higher value prime to that stored in fctr. Line 19 then stores the returned value in fctr, overwriting what was already in there. 
20 
endif. Housekeeping  closes ifendif clause opened in line 15. 
21 
until (temp
= 1)  (fctr > temp).
Housekeeping again, but much more involved. The code has
reached the end of the DO loop opened in line 14. A decision has to be made now: go around the DO loop again, or quit and move on to the next line of code? There are two exit conditions:
Either of these conditions means that all possible prime factors have been found. If neither is met, the DO loop is executed again, and will continue this way until one of the conditions is met. 
22 
endif. Housekeeping: closes ifendif clause opened in line 2. 
23 
return count. The program has finished at this point. All that remains to do is to return to the calling routine the value stored in variable count, which is equal now to the number of prime factors found in the vallue contained in the original argument p. 
MAIN MENU
HOW DOES IT WORK?
Site design/maintenance: Dave Ellis Email me!
Last Updated: February 4th, 2010.