Proper divisors: Difference between revisions
→{{header|ALGOL 68}}: Added alternative, faster proper divisor counting example.
(→{{header|ALGOL 68}}: Added alternative, faster proper divisor counting example.) |
|||
Line 301:
=={{header|ALGOL 68}}==
===As required by the Task===
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
<lang algol68># MODE to hold an element of a list of proper divisors #
Line 407 ⟶ 408:
Proper divisors of: 10: 1 2 5
15120 is the first number upto 20000 with 79 divisors
</pre>
===Faster Proper Divisor Counting===
Alternative version that uses a sieve-like approach for faster proper divisor counting.
<br>Note, this uses an array that is too large for ALGOL 68G under Windows.
<lang algol68>BEGIN # count proper divisors using a sieve-like approach #
# find the first/only number in 1 : 20 000 and 1 : 64 000 000 with #
# the most divisors #
INT max number := 20 000;
TO 2 DO
INT max divisors := 0;
INT has max divisors := 0;
INT with max divisors := 0;
[ 1 : max number ]INT pdc; pdc[ 1 ] := 0; FOR i FROM 2 TO UPB pdc DO pdc[ i ] := 1 OD;
FOR i FROM 2 TO UPB pdc DO
FOR j FROM i + i BY i TO UPB pdc DO pdc[ j ] +:= 1 OD
OD;
FOR d TO max number DO
INT divisor count = pdc[ d ];
IF divisor count > max divisors THEN
# found a number with more divisors than the previous max #
max divisors := divisor count;
has max divisors := d;
with max divisors := 1
ELIF divisor count = max divisors THEN
# found another number with that many divisors #
with max divisors +:= 1
FI
OD;
print( ( whole( has max divisors, 0 )
, " is the "
, IF with max divisors < 2 THEN "only" ELSE "first" FI
, " number upto "
, whole( max number, 0 )
, " with "
, whole( max divisors, 0 )
, " divisors"
, newline
)
);
max number := 64 000 000
OD
END</lang>
{{out}}
<pre>
15120 is the first number upto 20000 with 79 divisors
61261200 is the only number upto 64000000 with 719 divisors
</pre>
| |||