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^{30}  1073741824 
uint  2^{31}  2147483648 
int64  2^{61}  2305843009213693952 
uint64  2^{62}  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 linebyline exegesis of the code. 
1 
def sum, factor: int. Defines the two local variables to be used by the function, already described above. 
2 
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. 
3 
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 evennumbered prime factor, it's dealt with separately as a special case. 
4 
do.
Opens the DO loop associated with the case where the prime factor
is 2. Lines 4 through 9 deal exclusivesly with this case . 
5 
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?" 
6 
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. 
7 
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. 
8 
endif. Housekeeping  closes IFENDIF clause. 
9 
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." 
10 
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. 
11 
do. Opens the DO loop associated with odd prime factors only. 
12 
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." 
13 
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. 
14 
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. 
15 
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, overwriting what was already stored in there." It's reducting c's value ready for the next factor test. 
16 
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. 
17 
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. 
18 
endif. Housekeeping  closes inner IFENDIF clause. 
19 
else.
Housekeeping  provides alternate action if line 12 returns FALSE, that
is, the current value of factor
in that line wasn't prime. 
20 
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. 
21 
endif.
Housekeeping  closes the IFELSEENDIF clause originating in line 12. 
22 
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 oddnumber DO loop again or move
on. Thus, a paraphrase of line 22 could be "If the value of the
recentlydivided c is unity,
move on to the next line of code; if not, reexecute the DO loop from
line 11 again." 
23 
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. 
MAIN MENU
HOW DOES IT WORK?
Site design/maintenance: Dave Ellis Email me!
Last Updated: February 5th, 2010.