70 lines
1.6 KiB
Text
70 lines
1.6 KiB
Text
/* Find the sum of the digits of a number */
|
|
proc nonrec digitsum(word n) word:
|
|
word sum;
|
|
sum := 0;
|
|
while n ~= 0 do
|
|
sum := sum + n % 10;
|
|
n := n / 10
|
|
od;
|
|
sum
|
|
corp
|
|
|
|
/* Find all prime factors and write them into the given array
|
|
(which is assumed to be big enough); return the amount of
|
|
factors. */
|
|
proc nonrec factors(word n; [*] word facs) word:
|
|
word count, fac;
|
|
count := 0;
|
|
|
|
/* take out factors of 2 */
|
|
while n > 0 and n & 1 = 0 do
|
|
n := n >> 1;
|
|
facs[count] := 2;
|
|
count := count + 1
|
|
od;
|
|
|
|
/* take out odd factors */
|
|
fac := 3;
|
|
while n >= fac do
|
|
while n % fac = 0 do
|
|
n := n / fac;
|
|
facs[count] := fac;
|
|
count := count + 1;
|
|
od;
|
|
fac := fac + 2
|
|
od;
|
|
count
|
|
corp
|
|
|
|
/* See if a number is a Smith number */
|
|
proc nonrec smith(word n) bool:
|
|
[32] word facs; /* 32 factors ought to be enough for everyone */
|
|
word dsum, facsum, nfacs, i;
|
|
|
|
nfacs := factors(n, facs);
|
|
if nfacs = 1 then
|
|
false /* primes are not Smith numbers */
|
|
else
|
|
dsum := digitsum(n);
|
|
facsum := 0;
|
|
for i from 0 upto nfacs-1 do
|
|
facsum := facsum + digitsum(facs[i])
|
|
od;
|
|
dsum = facsum
|
|
fi
|
|
corp
|
|
|
|
/* Find all Smith numbers below 10000 */
|
|
proc nonrec main() void:
|
|
word i, count;
|
|
count := 0;
|
|
for i from 2 upto 9999 do
|
|
if smith(i) then
|
|
write(i:5);
|
|
count := count + 1;
|
|
if count & 0xF = 0 then writeln() fi
|
|
fi
|
|
od;
|
|
writeln();
|
|
writeln("Found ", count, " Smith numbers.")
|
|
corp
|