The   proper divisors   of a positive integer N are those numbers, other than N itself, that divide N without remainder.

For N > 1 they will always include 1,   but for N == 1 there are no proper divisors.



Examples

The proper divisors of     6     are   1, 2, and 3.

The proper divisors of   100   are   1, 2, 4, 5, 10, 20, 25, and 50.



Task

 Create a routine to generate all the proper divisors of a number.
 use it to show the proper divisors of the numbers 1 to 10 inclusive.
 Find a number in the range 1 to 20,000 with the most proper divisors. Show the number and just the count of how many proper divisors it has.


Show all output here.



Related tasks

   Amicable pairs
   Abundant, deficient and perfect number classifications
   Aliquot sequence classifications
   Factors of an integer
   Prime decomposition


 
MODULE ProperDivisors;
IMPORT
  Out;
 
CONST 
    initialSize = 128;
TYPE
  Result* = POINTER TO ResultDesc;
  ResultDesc = RECORD 
    found-: LONGINT; (* number of slots in pd *)
    pd-: POINTER TO ARRAY OF LONGINT;
    cap: LONGINT;   (* Capacity *)
  END;
 
VAR
  i,found,max,idxMx: LONGINT;
  mx: ARRAY 32 OF LONGINT;
  rs: Result;
 
  PROCEDURE (r: Result) Init(size: LONGINT);
  BEGIN 
    r.found := 0;
    r.cap := size;
    NEW(r.pd,r.cap);
  END Init;
 
  PROCEDURE (r: Result) Add(n: LONGINT);
  BEGIN
    (* Out.String("--->");Out.LongInt(n,0);Out.String(" At: ");Out.LongInt(r.found,0);Out.Ln; *)
    IF (r.found < LEN(r.pd^) - 1) THEN 
      r.pd[r.found] := n;
    ELSE
      (* expand pd for more room *)
    END;
    INC(r.found);
  END Add;
 
  PROCEDURE (r:Result) Show();
  VAR
    i: LONGINT;
  BEGIN
      Out.String("(Result:");Out.LongInt(r.found + 1,0);(* Out.String("/");Out.LongInt(r.cap,0);*)
      Out.String("-");
      IF r.found > 0 THEN
        FOR i:= 0 TO r.found - 1 DO
          Out.LongInt(r.pd[i],0);
          IF i = r.found - 1 THEN Out.Char(')') ELSE Out.Char(',') END
        END
      END;
      Out.Ln
  END Show;
 
  PROCEDURE (r:Result) Reset();
  BEGIN 
    r.found := 0;
  END Reset;
 
  PROCEDURE GetFor(n: LONGINT;VAR rs: Result);
  VAR
    i: LONGINT;
  BEGIN
    IF n > 1 THEN 
      rs.Add(1);i := 2;
      WHILE (i < n) DO
        IF (n MOD i) = 0 THEN rs.Add(i) END;
        INC(i)
      END
    END;
  END GetFor;
 
BEGIN
  NEW(rs);rs.Init(initialSize);
  FOR i := 1 TO 10 DO 
    Out.LongInt(i,4);Out.Char(':');
    GetFor(i,rs);
    rs.Show();
    rs.Reset();
  END;
  Out.LongInt(100,4);Out.Char(':');GetFor(100,rs);rs.Show();rs.Reset();
  max := 0;idxMx := 0;found := 0;
  FOR i := 1 TO 20000 DO
    GetFor(i,rs);
    IF rs.found > max THEN
      idxMx:= 0;mx[idxMx] := i;max := rs.found
    ELSIF rs.found = max THEN
      INC(idxMx);mx[idxMx] := i
    END;
    rs.Reset()
  END;
  Out.String("Found: ");Out.LongInt(idxMx + 1,0);
  Out.String(" Numbers with most proper divisors ");
  Out.LongInt(max,0);Out.String(": ");Out.Ln;
  FOR i := 0 TO idxMx DO
    Out.LongInt(mx[i],0);Out.Ln
  END
END ProperDivisors.
 