Proper divisors: Difference between revisions

Content added Content deleted

Inline

@@ Line 39: / Line 39: @@
 PROC proper divisors = ( INT n )REF DIVISORLIST:
      BEGIN
-         REF DIVISORLIST result := nil divisor list;
+         REF DIVISORLIST result   := nil divisor list;
-         INT abs n = ABS n;
+         REF DIVISORLIST end list := result;
+         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
+             INT root n = ENTIER sqrt( abs n );
+             FOR d FROM root n BY -1 TO 2 DO
                  IF abs n MOD d = 0 THEN
                      # found another divisor                      #
                      result := HEAP DIVISORLIST
-                            := DIVISORLIST( d, result )
+                            := DIVISORLIST( d, result );
+                     IF end list IS nil divisor list THEN
+                         # first result                           #
+                         end list := result
+                     FI;
+                     IF d * d /= n THEN
+                         # add the other divisor to the end of    #
+                         # the list                               #
+                         next OF end list := HEAP DIVISORLIST
+                                          := DIVISORLIST( abs n OVER d, nil divisor list );
+                         end list         := next OF end list
+                     FI
                  FI
              OD;