Largest proper divisor of n: Difference between revisions
→{{header|Haskell}}: Added a variant which only checks the first two proper divisors (if there are that many) |
→{{header|REXX}}: added the computer programming language REXX. |
||
Line 463: | Line 463: | ||
27 41 1 42 17 43 29 44 1 45 |
27 41 1 42 17 43 29 44 1 45 |
||
13 46 31 47 19 48 1 49 33 50</pre> |
13 46 31 47 19 48 1 49 33 50</pre> |
||
=={{header|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> |
|||
{{out|output|text= when using the default inputs:}} |
|||
<pre> |
|||
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 |
|||
───────┴─────────────────────────────────────────────────── |
|||
</pre> |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
Revision as of 18:29, 1 June 2021
- 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
<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
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
<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