72 lines
2.7 KiB
Text
72 lines
2.7 KiB
Text
# sieve of Eratosthene: sets s[i] to TRUE if i is prime, FALSE otherwise #
|
|
PROC sieve = ( REF[]BOOL s )VOID:
|
|
BEGIN
|
|
# start with everything flagged as prime #
|
|
FOR i TO UPB s DO s[ i ] := TRUE OD;
|
|
# sieve out the non-primes #
|
|
s[ 1 ] := FALSE;
|
|
FOR i FROM 2 TO ENTIER sqrt( UPB s ) DO
|
|
IF s[ i ] THEN FOR p FROM i * i BY i TO UPB s DO s[ p ] := FALSE OD FI
|
|
OD
|
|
END # sieve # ;
|
|
|
|
# construct a sieve of primes up to the maximum number required for the task #
|
|
INT max number = 10 000;
|
|
[ 1 : max number ]BOOL is prime;
|
|
sieve( is prime );
|
|
|
|
# returns the sum of the digits of n #
|
|
OP DIGITSUM = ( INT n )INT:
|
|
BEGIN
|
|
INT sum := 0;
|
|
INT rest := ABS n;
|
|
WHILE rest > 0 DO
|
|
sum +:= rest MOD 10;
|
|
rest OVERAB 10
|
|
OD;
|
|
sum
|
|
END # DIGITSUM # ;
|
|
|
|
# returns TRUE if n is a Smith number, FALSE otherwise #
|
|
# n must be between 1 and max number #
|
|
PROC is smith = ( INT n )BOOL:
|
|
IF is prime[ ABS n ] THEN
|
|
# primes are not Smith numbers #
|
|
FALSE
|
|
ELSE
|
|
# find the factors of n and sum the digits of the factors #
|
|
INT rest := ABS n;
|
|
INT factor digit sum := 0;
|
|
INT factor := 2;
|
|
WHILE factor < max number AND rest > 1 DO
|
|
IF NOT is prime[ factor ] THEN
|
|
# factor isn't a prime #
|
|
factor +:= 1
|
|
ELSE
|
|
# factor is a prime #
|
|
IF rest MOD factor /= 0 THEN
|
|
# factor isn't a factor of n #
|
|
factor +:= 1
|
|
ELSE
|
|
# factor is a factor of n #
|
|
rest OVERAB factor;
|
|
factor digit sum +:= DIGITSUM factor
|
|
FI
|
|
FI
|
|
OD;
|
|
( factor digit sum = DIGITSUM n )
|
|
FI # is smith # ;
|
|
|
|
# print all the Smith numbers below the maximum required #
|
|
INT smith count := 0;
|
|
FOR n TO max number - 1 DO
|
|
IF is smith( n ) THEN
|
|
# have a smith number #
|
|
print( ( whole( n, -7 ) ) );
|
|
smith count +:= 1;
|
|
IF smith count MOD 10 = 0 THEN
|
|
print( ( newline ) )
|
|
FI
|
|
FI
|
|
OD;
|
|
print( ( newline, "THere are ", whole( smith count, -7 ), " Smith numbers below ", whole( max number, -7 ), newline ) )
|