Proper divisors: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: Added alternative, faster proper divisor counting example.) |
|||
Line 301: | Line 301: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
===As required by the Task=== |
|||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{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 # |
<lang algol68># MODE to hold an element of a list of proper divisors # |
||
Line 407: | Line 408: | ||
Proper divisors of: 10: 1 2 5 |
Proper divisors of: 10: 1 2 5 |
||
15120 is the first number upto 20000 with 79 divisors |
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> |
</pre> |
||