Proper divisors: Difference between revisions
Content added Content deleted
m (→version 3: added whitespace and highlighting in the REXX section header.) |
(Added Algol 68) |
||
| Line 26: | Line 26: | ||
* [[Prime decomposition]] |
* [[Prime decomposition]] |
||
<br><br> |
<br><br> |
||
=={{header|ALGOL 68}}== |
|||
{{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 # |
|||
MODE DIVISORLIST = STRUCT( INT divisor, REF DIVISORLIST next ); |
|||
# end of divisor list value # |
|||
REF DIVISORLIST nil divisor list = REF DIVISORLIST(NIL); |
|||
# resturns a DIVISORLIST containing the proper divisors of n # |
|||
# if n = 1, 0 or -1, we return no divisors # |
|||
PROC proper divisors = ( INT n )REF DIVISORLIST: |
|||
BEGIN |
|||
REF DIVISORLIST result := nil divisor list; |
|||
INT abs n = ABS n; |
|||
IF abs n > 1 THEN |
|||
# build the list of divisors backeards, so they are # |
|||
# returned in ascending order # |
|||
FOR d FROM abs n - 1 BY -1 TO 2 DO |
|||
IF abs n MOD d = 0 THEN |
|||
# found another divisor # |
|||
result := HEAP DIVISORLIST |
|||
:= DIVISORLIST( d, result ) |
|||
FI |
|||
OD; |
|||
# 1 is always a proper divisor of numbers > 1 # |
|||
result := HEAP DIVISORLIST |
|||
:= DIVISORLIST( 1, result ) |
|||
FI; |
|||
result |
|||
END # proper divisors # ; |
|||
# returns the number of divisors in a DIVISORLIST # |
|||
PROC count divisors = ( REF DIVISORLIST list )INT: |
|||
BEGIN |
|||
INT result := 0; |
|||
REF DIVISORLIST divisors := list; |
|||
WHILE divisors ISNT nil divisor list DO |
|||
result +:= 1; |
|||
divisors := next OF divisors |
|||
OD; |
|||
result |
|||
END # count divisors # ; |
|||
# find the proper divisors of 1 : 10 # |
|||
FOR n TO 10 DO |
|||
REF DIVISORLIST divisors := proper divisors( n ); |
|||
print( ( "Proper divisors of: ", whole( n, -2 ), ": " ) ); |
|||
WHILE divisors ISNT nil divisor list DO |
|||
print( ( " ", whole( divisor OF divisors, 0 ) ) ); |
|||
divisors := next OF divisors |
|||
OD; |
|||
print( ( newline ) ) |
|||
OD; |
|||
# find the first/only number in 1 : 20 000 with the most divisors # |
|||
INT max number = 20 000; |
|||
INT max divisors := 0; |
|||
INT has max divisors := 0; |
|||
INT with max divisors := 0; |
|||
FOR d TO max number DO |
|||
INT divisor count = count divisors( proper divisors( 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 |
|||
) )</lang> |
|||
{{out}} |
|||
<pre> |
|||
Proper divisors of: 1: |
|||
Proper divisors of: 2: 1 |
|||
Proper divisors of: 3: 1 |
|||
Proper divisors of: 4: 1 2 |
|||
Proper divisors of: 5: 1 |
|||
Proper divisors of: 6: 1 2 3 |
|||
Proper divisors of: 7: 1 |
|||
Proper divisors of: 8: 1 2 4 |
|||
Proper divisors of: 9: 1 3 |
|||
Proper divisors of: 10: 1 2 5 |
|||
15120 is the first number upto 20000 with 79 divisors |
|||
</pre> |
|||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
| Line 83: | Line 179: | ||
18480 79 divisors not shown |
18480 79 divisors not shown |
||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
C has tedious boilerplate related to allocating memory for dynamic arrays, so we just skip the problem of storing values altogether. |
C has tedious boilerplate related to allocating memory for dynamic arrays, so we just skip the problem of storing values altogether. |
||