PrimeFactorSum

FUNCTION: PrimeFactorSum(). Pass an integer to this function and it will generate all its prime factors, totalise them, and return the sum to the calling routine.

Note that this function uses another function: IsPrime(). Obviously, you must include IsPrime() with PrimeFactorSum() for the latter to work. To obtain a copy, click here 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³⁰	1073741824
uint	2³¹	2147483648
int64	2⁶¹	2305843009213693952
uint64	2⁶²	4611686018427387904

Declaring the function must be done like this:

declare PrimeFactorSum(c: int) (or whatever integer type you want).

Here's the code:

sub PrimeFactorSum(c)
' finds the prime factors of argument c
' and returns their sum
def sum, factor: int
sum = 0: 'intialise sum to zero

' look for factor 2
factor = 2
do
    if c % factor = 0: '2 is a factor
        sum = sum + factor: 'add it to sum
        c = c/factor: 'divide c by 2
    endif
until c % factor <> 0: 'until 2 not a factor

' look for factors greater than 2
factor = 3
do
    if IsPrime(factor): 'ensure factor is prime
        if c % factor = 0: 'is it a factor?
            sum = sum + factor: 'add it to sum
            c = c/factor: 'divide c by factor
        else
            factor = factor + 2: 'get next odd factor
        endif
    else
        factor = factor + 2: 'get next odd factor
    endif
until c = 1: 'no more factors possible
return sum

There are only two local variables. Variable sum, which holds the sum of the prime factors. This is initialised to zero, and gradually increases as the function progresses, until it holds the full sum. Variable factor holds the factor currently being tested.

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 sum, factor: int
sum = 0: 'intialise sum to zero
factor = 2
do
    if c % factor = 0: '2 is a factor
        sum = sum + factor: 'add it to sum
        c = c/factor: 'divide c by 2
    endif
until c % factor <> 0: 'until 2 not a factor
factor = 3
do
    if IsPrime(factor): 'ensure factor is prime
        if c % factor = 0: 'is it a factor?
            sum = sum + factor: 'add it to sum
            c = c/factor: 'divide c by factor
        else
            factor = factor + 2: 'get next odd factor
        endif
    else
        factor = factor + 2: 'get next odd factor
    endif
until c = 1: 'no more factors possible
return sum

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

def sum, factor: int. Defines the two local variables to be used by the function, already described above.

sum = 0. Initialises variable sum to zero. By the time sum is returned to the calling routine, it will hold the PFS (prime factor sum) of the argument.

factor = 2. Variable factor is initialised to two. This is the lowest possible prime factor of any number (and the commonest). Because it's the only even-numbered prime factor, it's dealt with separately as a special case.

do. Opens the DO loop associated with the case where the prime factor is 2. Lines 4 through 9 deal exclusivesly with this case .

if c % factor = 0. A simple way to find out if a prime number is a prime factor of another, larger number is to divide the larger number by the smaller and check for a remainder. If there is no remainder, we have found a prime factor. This line makes the check by using integer arithmetic. The percentage (%) sign means "make a division and discard all the result except for the remainder. So this line can be paraphrased as "Is the remainder when dividing argument c by variable factor zero?"

sum = sum + factor. This line is only executed if the answer to the question in line 5 is "yes." That means that variable factor (2 in this case) is a prime factor of argument c. So we can add factor to variable sum, which is totalising all the prime factors of the argument.

c = c/factor. Line 7 is critical to the function. Having found a prime factor of argument c, it's necessary to reformat c so that the next prime factor can be investigated. Remember, it could be the same number. For instance, the prime factors of 8 are 2, 2, and 2.

The "reformatting" is simple: just divide c by the prime factor itself and start again. Note that we can be certain this division is possible because the check in line 5 told us there would be no remainder.

Take a closer look at the example of 8 above. When the first prime factor, 2, has been found, add it to sum. The latter was initialised to zero, so it now equals 2. Now divide c by 2 to leave 4. 2 is again a factor of 4, so it's added to sum making sum equal 4. c is once again divided to 2. 4/2 = 2, so c is now 2. 2 is a prime factor of 2, so it's added to sum to make sum equal 6. If we go on to divide c by 2 again, there will be a remainder, so the process stops, giving PFS(8) = 6, the correct answer.

endif. Housekeeping - closes IF-ENDIF clause.

until c % factor <> 0. Line 9 marks the end of the DO loop associated with prime factor 2. A decision must be made: should the DO loop be executed again, or is it time for the code to move on to the next line? The repeated divisions made in the example above depended on the fact that there was never a remainder when c was divided by factor, which means factor is a prime factor of c. As soon as a remainder is encountered, we know that factor cannot be a prime factor of c. So line 9 can be expressed this way: "If variable c divides exactly by factor, execute the DO loop again; if not, quit the loop."

factor = 3. This line is only reached after all the prime factors 2 have been found and totalised in sum. Now we move on to the first odd prime factor, 3. All subsequent prime factors to be investigated will be odd, since 2 was the only prime factor there is. So variable factor is set to 3 ready to work on the odd prime factors.

do. Opens the DO loop associated with odd prime factors only.

if IsPrime(factor). Now that we're working with odd number values for factor, we have to be careful: not all odd numbers are prime. for example, 9 isn't prime but 11 is, and so on. Only prime numbers can also be prime factors, so a check on primality is made, using function IsPrime(). As explained in the introducty remarks above, you will have to include this function with the PrimeFactorSum() code. A link is provided to obtain the code. This line is therefore effectively saying "If the current value of variable factor is prime, execute the code in lines 13 through 18; if not, go to line 19 to be given alternative instructions."

if c % factor = 0. Works in exactly the same way as line 5, except that the value of factor will now be an odd number instead of 2.

c = c/factor. This command can be paraphrased as "Divide the value stored in argument c by the value stored in variable factor and save the result in c, over-writing what was already stored in there." It's reducting c's value ready for the next factor test.

else. If it was found in line 13 that the current value in variable factor didn't divide exactly into c's current value, we need to take alternate action. The else here prepares for that.

factor = factor + 2. The alternate action is to try the next higher permissible value for factor. Since we're only dealing with odd numbers now, factor is incremented by 2 to keep it odd.

endif. Housekeeping - closes inner IF-ENDIF clause.

else. Housekeeping - provides alternate action if line 12 returns FALSE, that is, the current value of factor in that line wasn't prime.

factor = factor + 2. And this is the alternate action to line 12 - try the next higher value of factor which is still an odd number.

endif. Housekeeping - closes the IF-ELSE-ENDIF clause originating in line 12.

until c = 1. We are dividing c by each prime factor it finds. Eventually, the last division will leave a remainder of 1. When this happens, all the prime factors have been found. Line 22 is therefore providing a test whose result decides whether to execute the odd-number DO loop again or move on. Thus, a paraphrase of line 22 could be "If the value of the recently-divided c is unity, move on to the next line of code; if not, re-execute the DO loop from line 11 again."

return sum. When the code reaches this line, all prime factors have been found and totalised into variable sum. All that remains to be done is to return this value to the calling routine, and line 23 does just that.

Finally, let's do a table of working results for an argument of, say, 84.

c	factor	c/factor	PF's	sum	comments
84	2	42	2	2	Using line 4 DO loop
42	2	21	2	4	Using line 4 DO loop
21	3	7	3	7	Using line 11 DO loop
7	7	1	7	14	Using line 11 DO loop
1					c = 1: finished

Note the way in which the original argument c is steadily reduced from 84 to 1 as the function progresses. At the same time, the value in variable sum, which was initialised to zero, gradually increases to 14. If you look down the PF (prime factors) column, you can see how they're discovered in order: 2, 2, 3, 7.