THE PUZZLET PAGE


How_Does_It_Work


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 230 1073741824
uint 231 2147483648
int64 261 2305843009213693952
uint64 262 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.

CountPrimeFactors() FlowChart

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, over-writing 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 line-by-line exegesis of the code.

1

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

count   Counts the prime factors as they are found.
temp   Manipulates a copy of variable p.
fctr   Holds prime numbers to check as factors.

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, over-writing what was previously stored in there.

11

endif.  Housekeeping: closes the if-endif 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 if-endif 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:

Condition Meaning


temp = 1 The value stored in variable temp, which has been progressively reduced by the code, has reached unity (1).
fctr > temp The value stored in variable fctr, which has been progressively increased by the code, has exceeded that stored in variable temp.

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 if-endif 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 E-mail me!
Last Updated: February 4th, 2010.