Largest proper divisor of n

Largest proper divisor of n is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Task

a(1) = 1; for n > 1, a(n) = largest proper divisor of n, where n < 101 .

ALGOL 68

<lang algol68>FOR n TO 100 DO # show the largest proper divisors for n = 1..100 #

   INT largest proper divisor := 1;
   FOR j FROM ( n OVER 2 ) BY -1 TO 2 WHILE largest proper divisor = 1 DO
       IF n MOD j = 0 THEN
           largest proper divisor := j
       FI
   OD;
   print( ( whole( largest proper divisor, -3 ) ) );
   IF n MOD 10 = 0 THEN print( ( newline ) ) FI

OD </lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

ALGOL W

<lang algolw>for n := 1 until 100 do begin % show the largest proper divisors for n = 1..100 %

   for j := n div 2 step -1 until 2 do begin
       if n rem j = 0 then begin
           writeon( i_w := 3, s_w := 0, j );
           goto foundLargestProperDivisor
       end if_n_rem_j_eq_0
   end for_j;
   writeon( i_w := 3, s_w := 0, 1 );

foundLargestProperDivisor:

   if n rem 10 = 0 then write()

end for_n.</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

APL

Works with: Dyalog APL

<lang apl>(⌈/1,(⍸0=¯1↓⍳|⊢))¨10 10⍴⍳100</lang>

Output:

 1  1  1  2  1  3  1  4  3  5
 1  6  1  7  5  8  1  9  1 10
 7 11  1 12  5 13  9 14  1 15
 1 16 11 17  7 18  1 19 13 20
 1 21  1 22 15 23  1 24  7 25
17 26  1 27 11 28 19 29  1 30
 1 31 21 32 13 33  1 34 23 35
 1 36  1 37 25 38 11 39  1 40
27 41  1 42 17 43 29 44  1 45
13 46 31 47 19 48  1 49 33 50

BASIC

<lang basic>10 DEFINT A-Z 20 FOR I=1 TO 100 30 IF I=1 THEN PRINT " 1";: GOTO 70 40 FOR J=I-1 TO 1 STEP -1 50 IF I MOD J=0 THEN PRINT USING "###";J;: GOTO 70 60 NEXT J 70 IF I MOD 10=0 THEN PRINT 80 NEXT I</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

BCPL

<lang bcpl>get "libhdr"

let lpd(n) = valof

   for i = n<=1 -> 1, n-1 to 1 by -1
       if n rem i=0 resultis i

let start() be

   for i=1 to 100
   $(  writed(lpd(i), 3)
       if i rem 10=0 then wrch('*N')
   $)</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

C

<lang c>#include <stdio.h>

unsigned int lpd(unsigned int n) {

   if (n<=1) return 1;
   int i;
   for (i=n-1; i>0; i--)
       if (n%i == 0) return i;   

}

int main() {

   int i;
   for (i=1; i<=100; i++) {
       printf("%3d", lpd(i));
       if (i % 10 == 0) printf("\n");
   }
   return 0;

}</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Cowgol

<lang cowgol>include "cowgol.coh";

sub print3(n: uint8) is

   print_char(' ');
   if n>9 then
       print_char('0' + n/10);
   else
       print_char(' ');
   end if;
   print_char('0' + n%10);

end sub;

sub lpd(n: uint8): (r: uint8) is

   if n <= 1 then
       r := 1;
   else
       r := n - 1;
       while r > 0 loop
           if n % r == 0 then 
               break;
           end if;
           r := r - 1;
       end loop;
   end if;

end sub;

var i: uint8 := 1; while i <= 100 loop

   print3(lpd(i));
   if i%10 == 0 then
       print_nl();
   end if;
   i := i + 1;

end loop;</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

FOCAL

<lang focal>01.10 F N=1,100;D 2;D 3 01.20 Q

02.10 S V=1 02.20 I (1-N)2.3;R 02.30 S V=N-1 02.40 S A=N/V 02.50 I (FITR(A)-A)2.6;R 02.60 S V=V-1 02.70 G 2.4

03.10 T %2,V 03.20 S A=N/10 03.30 I (FITR(A)-A)3.4;T ! 03.40 R</lang>

Output:

=  1=  1=  1=  2=  1=  3=  1=  4=  3=  5
=  1=  6=  1=  7=  5=  8=  1=  9=  1= 10
=  7= 11=  1= 12=  5= 13=  9= 14=  1= 15
=  1= 16= 11= 17=  7= 18=  1= 19= 13= 20
=  1= 21=  1= 22= 15= 23=  1= 24=  7= 25
= 17= 26=  1= 27= 11= 28= 19= 29=  1= 30
=  1= 31= 21= 32= 13= 33=  1= 34= 23= 35
=  1= 36=  1= 37= 25= 38= 11= 39=  1= 40
= 27= 41=  1= 42= 17= 43= 29= 44=  1= 45
= 13= 46= 31= 47= 19= 48=  1= 49= 33= 50

Fortran

<lang fortran> program LargestProperDivisors

      implicit none
      integer i, lpd
      do 10 i=1, 100
          write (*,'(I3)',advance='no') lpd(i)
10        if (i/10*10 .eq. i) write (*,*)       
      end program
      
      integer function lpd(n)
      implicit none
      integer n, i
      if (n .le. 1) then
          lpd = 1
      else
          do 10 i=n-1, 1, -1
10            if (n/i*i .eq. n) goto 20
20        lpd = i
      end if
      end function</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Haskell

<lang haskell>import Data.List.Split (chunksOf) import Text.Printf (printf)

lpd :: Int -> Int lpd 1 = 1 lpd n = head [x | x <- [n -1, n -2 .. 1], n `mod` x == 0]

main :: IO () main =

 (putStr . unlines . map concat . chunksOf 10) $
    printf "%3d" . lpd <$> [1 .. 100]</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Or, considering the two smallest proper divisors:

(If there are two, then the largest proper divisor will be N divided by the first proper divisor that is not 1)

(Otherwise, the largest proper divisor will be 1 itself).

<lang haskell>import Data.List.Split (chunksOf) import Text.Printf (printf)

maxProperDivisors :: Int -> Int maxProperDivisors n

 | 1 < length ab = quot n (last ab)
 | otherwise = 1
   where
     root = (floor . sqrt) (fromIntegral n :: Double)
     ab = take 2 $ [1 .. root] >>= (\x -> [x | 0 == rem n x]) 
      

main :: IO () main =

 (putStr . unlines . map concat . chunksOf 10) $
    printf "%3d" . maxProperDivisors <$> [1 .. 100]</lang>

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

MAD

<lang MAD> NORMAL MODE IS INTEGER

           INTERNAL FUNCTION(N)
           ENTRY TO LPD.
           WHENEVER N.LE.1, FUNCTION RETURN 1
           THROUGH TEST, FOR D=N-1, -1, D.L.1

TEST WHENEVER N/D*D.E.N, FUNCTION RETURN D

           END OF FUNCTION
           
           THROUGH SHOW, FOR I=1, 10, I.GE.100

SHOW PRINT FORMAT TABLE,

         0     LPD.(I), LPD.(I+1), LPD.(I+2), LPD.(I+3),
         1     LPD.(I+4), LPD.(I+5), LPD.(I+6), LPD.(I+7),
         2     LPD.(I+8), LPD.(I+9)
         
           VECTOR VALUES TABLE = $10(I3)*$
           END OF PROGRAM </lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Pascal

<lang pascal> program LarPropDiv;

function LargestProperDivisor(n:NativeInt):NativeInt; //searching upwards to save time for example 100 //2..sqrt(n) aka 1..10 instead downwards n..sqrt(n) 100..10 var

 i,j: NativeInt;

Begin

 i := 2;
 repeat
   If n Mod i = 0 then
   Begin
     LargestProperDivisor := n DIV i;
     EXIT;
   end;
   inc(i);
 until i*i > n;
 LargestProperDivisor := 1;

end; var

 n : Uint32;

begin

 for n := 1 to 100 do
 Begin
   write(LargestProperDivisor(n):4);
   if n mod 10 = 0 then
     Writeln;
 end;

end.</lang>

Output:

   1   1   1   2   1   3   1   4   3   5
   1   6   1   7   5   8   1   9   1  10
   7  11   1  12   5  13   9  14   1  15
   1  16  11  17   7  18   1  19  13  20
   1  21   1  22  15  23   1  24   7  25
  17  26   1  27  11  28  19  29   1  30
   1  31  21  32  13  33   1  34  23  35
   1  36   1  37  25  38  11  39   1  40
  27  41   1  42  17  43  29  44   1  45
  13  46  31  47  19  48   1  49  33  50

Phix

puts(1,join_by(apply(true,sprintf,{{"%3d"},vslice(apply(apply(true,factors,{tagset(100),-1}),reverse),1)}),1,10,""))

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Alternative, same output, optimised: obviously checking for a factor from 2 up is going to be significantly faster than n-1 down... at least on much larger numbers, that is.

with javascript_semantics
for n=1 to 100 do
    integer p = 2,
            lim = floor(sqrt(n)),
            hf = 1
    while p<=lim do
        if remainder(n,p)=0 then
            hf = n/p
            exit
        end if
        p += 1
    end while 
    printf(1,"%3d",hf)
    if remainder(n,10)=0 then puts(1,"\n") end if
end for

PL/M

<lang plm>100H: BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS; EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT; PUT$CHAR: PROCEDURE (CH); DECLARE CH BYTE; CALL BDOS(2,CH); END PUT$CHAR; PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;

PRINT$3: PROCEDURE (N);

   DECLARE N BYTE;
   CALL PUT$CHAR(' ');
   IF N>9
       THEN CALL PUT$CHAR('0' + N/10);
       ELSE CALL PUT$CHAR(' ');
   CALL PUT$CHAR('0' + N MOD 10);

END PRINT$3;

LPD: PROCEDURE (N) BYTE;

   DECLARE (N, I) BYTE;
   IF N <= 1 THEN RETURN 1;
   I = N-1;
   DO WHILE I >= 1;
       IF N MOD I = 0 THEN RETURN I;
       I = I - 1;
   END;

END LPD;

DECLARE I BYTE; DO I=1 TO 100;

   CALL PRINT$3(LPD(I));
   IF I MOD 10 = 0 THEN CALL PRINT(.(13,10,'$'));

END; CALL EXIT; EOF</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Python

<lang python>def lpd(n):

   for i in range(n-1,0,-1):
       if n%i==0: return i
   return 1

for i in range(1,101):

   print("{:3}".format(lpd(i)), end=i%10==0 and '\n' or )</lang>

Output:

  1  1  1  2  1  3  1  4  3  5
  1  6  1  7  5  8  1  9  1 10
  7 11  1 12  5 13  9 14  1 15
  1 16 11 17  7 18  1 19 13 20
  1 21  1 22 15 23  1 24  7 25
 17 26  1 27 11 28 19 29  1 30
  1 31 21 32 13 33  1 34 23 35
  1 36  1 37 25 38 11 39  1 40
 27 41  1 42 17 43 29 44  1 45
 13 46 31 47 19 48  1 49 33 50

Raku

A little odd to special case a(1) == 1 as technically, 1 doesn't have any proper divisors... but it matches OEIS A032742 so whatever. <lang perl6>use Prime::Factor;

say (flat 1, (2..100).map: *.&proper-divisors.sort.tail ).batch(10)».fmt("%2d").join: "\n";</lang>

Output:

 1  1  1  2  1  3  1  4  3  5
 1  6  1  7  5  8  1  9  1 10
 7 11  1 12  5 13  9 14  1 15
 1 16 11 17  7 18  1 19 13 20
 1 21  1 22 15 23  1 24  7 25
17 26  1 27 11 28 19 29  1 30
 1 31 21 32 13 33  1 34 23 35
 1 36  1 37 25 38 11 39  1 40
27 41  1 42 17 43 29 44  1 45
13 46 31 47 19 48  1 49 33 50

REXX

<lang rexx>/*REXX program finds the largest proper divisors of all numbers (up to a given limit). */ parse arg n cols . /*obtain optional argument from the CL.*/ if n== | n=="," then n= 101 /*Not specified? Then use the default.*/ if cols== | cols=="," then cols= 10 /* " " " " " " */ w= length(n) + 1 /*W: the length of any output column. */ @LPD = "largest proper divisor of N, where N < " n idx = 1 /*initialize the index (output counter)*/ say ' index │'center(@LPD, 1 + cols*(w+1) ) /*display the title for the output. */ say '───────┼'center("" , 1 + cols*(w+1), '─') /* " " sep " " " */ $= /*a list of largest proper divs so far.*/

    do j=1  for n-1;  $= $ right(LPDIV(j), w)   /*add a largest proper divisor ──► list*/
    if j//cols\==0  then iterate                /*have we populated a line of output?  */
    say center(idx, 7)'│'  substr($, 2);   $=   /*display what we have so far  (cols). */
    idx= idx + cols                             /*bump the  index  count for the output*/
    end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say '───────┴'center("" , 1 + cols*(w+1), '─') /*display the foot separator. */ exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ LPDIV: procedure; parse arg x; if x<4 then return 1 /*obtain X; test if X < 4. */

                do k=x%2  by -1                 /*start at halfway point and decrease. */
                if x//k==0  then return k       /*No remainder?  Got largest proper div*/
                end   /*k*/
                                 return 1       /*the number  X  is a prime.           */</lang>

output   when using the default inputs:

 index │  largest proper divisor of  N,  where  N  <  101
───────┼───────────────────────────────────────────────────
   1   │    1    1    1    2    1    3    1    4    3    5
  11   │    1    6    1    7    5    8    1    9    1   10
  21   │    7   11    1   12    5   13    9   14    1   15
  31   │    1   16   11   17    7   18    1   19   13   20
  41   │    1   21    1   22   15   23    1   24    7   25
  51   │   17   26    1   27   11   28   19   29    1   30
  61   │    1   31   21   32   13   33    1   34   23   35
  71   │    1   36    1   37   25   38   11   39    1   40
  81   │   27   41    1   42   17   43   29   44    1   45
  91   │   13   46   31   47   19   48    1   49   33   50
───────┴───────────────────────────────────────────────────

Ring

<lang ring> see "working..." + nl see "Largest proper divisor of n are:" + nl see "1 " row = 1 limit = 100

for n = 2 to limit

   for m = 1 to n-1 
       if n%m = 0
          div = m
       ok
   next
   row = row + 1
   see "" + div + " "
   if row%10 = 0
      see nl
   ok

next

see "done..." + nl </lang>

Output:

working...
Largest proper divisor of n are:
1 1 1 2 1 3 1 4 3 5 
1 6 1 7 5 8 1 9 1 10 
7 11 1 12 5 13 9 14 1 15 
1 16 11 17 7 18 1 19 13 20 
1 21 1 22 15 23 1 24 7 25 
17 26 1 27 11 28 19 29 1 30 
1 31 21 32 13 33 1 34 23 35 
1 36 1 37 25 38 11 39 1 40 
27 41 1 42 17 43 29 44 1 45 
13 46 31 47 19 48 1 49 33 50 
done...

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/fmt" for Fmt

System.print("The largest proper divisors for numbers in the interval [1, 100] are:") System.write(" 1 ") for (n in 2..100) {

   if (n % 2 == 0) {
       Fmt.write("$2d  ", n / 2)
   } else {
       Fmt.write("$2d  ", Int.properDivisors(n)[-1])
   }
   if (n % 10 == 0) System.print()

}</lang>

Output:

The largest proper divisors for numbers in the interval [1, 100] are:
 1   1   1   2   1   3   1   4   3   5  
 1   6   1   7   5   8   1   9   1  10  
 7  11   1  12   5  13   9  14   1  15  
 1  16  11  17   7  18   1  19  13  20  
 1  21   1  22  15  23   1  24   7  25  
17  26   1  27  11  28  19  29   1  30  
 1  31  21  32  13  33   1  34  23  35  
 1  36   1  37  25  38  11  39   1  40  
27  41   1  42  17  43  29  44   1  45  
13  46  31  47  19  48   1  49  33  50