Rosetta Code

Largest proper divisor of n: Difference between revisions

Page Discussion

Largest proper divisor of n (view source)

Revision as of 10:07, 15 December 2023

5,584 bytes added ,  5 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(15 intermediate revisions by 8 users not shown)
Line 542:
{{trans|FreeBASIC}}
{{works with|Decimal BASIC}}
{{works with|IS-BASIC}}
<syntaxhighlight lang="basic">
100 REM Largest proper divisor of n
Line 552 ⟶ 553:
170 PRINT USING "###": J;
180 EXIT FOR
290190 END IF
200 NEXT J
210 IF MOD(I, 10) = 0 THEN PRINT
Line 723 ⟶ 724:
{{works with|BASICA}}
{{trans|FreeBASIC}}
{{works with|IS-BASIC}}
<syntaxhighlight lang="qbasic">100 PRINT "El mayor divisor propio de n es:"
110 PRINT
Line 827 ⟶ 829:
220 IF j >= 10 THEN PRINT " "; j;
230 GOTO 160</syntaxhighlight>
 
==={{header|Run BASIC}}===
<syntaxhighlight lang="vbnet">print "Largest proper divisor of n is:"
print chr$(10)+" 1 1";
for i = 3 to 100
for j = i-1 to 1 step -1
if i mod j = 0 then print using("###",j); : goto [exit]
next j
[exit]
if i mod 10 = 0 then print
next i
end</syntaxhighlight>
 
==={{Header|Tiny BASIC}}===
Line 1,062 ⟶ 1,076:
27 41 1 42 17 43 29 44 1 45
13 46 31 47 19 48 1 49 33 50</pre>
 
=={{header|D}}==
 
{{trans|C}}
 
<syntaxhighlight lang="d">
import std.stdio;
import std.range;
import std.algorithm;
 
uint lpd(uint n) {
if (n <= 1) {
return 1;
}
 
auto divisors = array(iota(1, n).filter!(i => n % i == 0));
 
return divisors.empty ? 1 : divisors[$ - 1];
}
 
void main() {
foreach (i; 1 .. 101) {
writef("%3d", lpd(i));
 
if (i % 10 == 0) {
writeln();
}
}
}
</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|Dart}}==
<syntaxhighlight lang="dart">import "dart:io";
import "dart:io";
 
num largest_proper_divisor(int n) {
Line 1,081 ⟶ 1,140:
print(largest_proper_divisor(n) + n % 10 == 0 ? "\n" : " ");
}
}
}</syntaxhighlight>
</syntaxhighlight>
{{out}}
<pre>Same as FreeBASIC entry.</pre>
Line 1,165 ⟶ 1,225:
 
=={{header|EasyLang}}==
<syntaxhighlight lang="easylang">
func lpdiv v .
r = 1
Line 1,175 ⟶ 1,235:
return r
.
numfmt 0 3
for i = 1 to 100
write lpdiv i & " "
if i mod 10 = 0
print ""
.
.
</syntaxhighlight>
Line 1,451 ⟶ 1,507:
 
=={{header|J}}==
<syntaxhighlight lang="j"> lpd =: (1 |}.!.1 ])&.q:</syntaxhighlight>
{{out}}
<pre>
lpd 1+>: i.100 5 20
1 1 1 2 1 3 1 4 3 5 1 6 1 7 5 8 1 9 1 10
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 ...</pre>
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
</pre>
 
This works by prime factorization of n, replacingremoving the largestsmallest prime factor with 1, and then taking the product of this new list of prime factors. In J terms, we work "under" factorization, in analogy to a medical operation where the patient is "under" anaethesiaanesthesia: (put patient to sleep) rearrange guts (wake patient up).
 
The core logic only concerns itself with a list of prime factors; it is never even aware of the original input integer, nor the final integer result. In fact, note that the final multiplication is implicit and never spelled out by the programmer; product is the inverse of factorization, and we requested to work "under" factorization, thus J's algebra knows to apply the inverse of factorization (i.e. taking the product) as the final step.
 
=={{header|Java}}==
Line 1,564 ⟶ 1,625:
27 41 1 42 17 43 29 44 1 45
13 46 31 47 19 48 1 49 33 50
</pre>
 
=={{header|Lua}}==
{{Trans|ALGOL 68}}
<syntaxhighlight lang="lua">
for n = 1, 100 do -- show the largest proper divisors for n = 1..100
local largestProperDivisor, j = 1, math.floor( n / 2 )
while j >= 2 and largestProperDivisor == 1 do
if n % j == 0 then
largestProperDivisor = j
end
j = j - 1
end
io.write( string.format( "%3d", largestProperDivisor ) )
if n % 10 == 0 then io.write( "\n" ) end
end
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
Line 1,718 ⟶ 1,808:
27 41 1 42 17 43 29 44 1 45
13 46 31 47 19 48 1 49 33 50</pre>
===Alternative (sieve)===
Most solutions use a function that returns the largest proper divisor of an individual integer. This console program, written in Free Pascal, applies a sieve to the integers 1..100 (or other limit).
<syntaxhighlight lang="pascal">
program LPD;
(*
Displays largest proper divisor for each integer in range 1..limit.
Command line:
LPD limit items_per_line
or LPD limit // items_per_line defaults to 10
or LPD // limit defaults to 100
*)
{$mode objfpc}{$H+}
 
uses SysUtils;
var
limit, items_per_line, nr_items, j, p : integer;
a : array of integer;
begin
// Set up defaults
limit := 100;
items_per_line := 10;
// Overwrite defaults with command-line parameters, if present
if ParamCount > 0 then
limit := SysUtils.StrToInt( ParamStr(1));
if ParamCount > 1 then
items_per_line := SysUtils.StrToInt( ParamStr(2));
WriteLn( 'Largest proper divisors 1..', limit);
// Dynamic arrays are 0-based. To keep it simple, we ignore a[0]
// and use a[j] for the integer j, 1 <= j <= limit
SetLength( a, limit + 1);
for j := 1 to limit do a[j] := 1; // stays at 1 if j is 1 or prime
 
// Sieve; if j is composite then a[j] := smallest prime factor of j
p := 2; // p = next prime
while p*p < limit do begin
j := 2*p;
while j <= limit do begin
if a[j] = 1 then a[j] := p;
inc( j, p);
end;
repeat
inc(p);
until (p > limit) or (a[p] = 1);
end;
 
// If j is composite, divide j by its smallest prime factor
for j := 1 to limit do
if a[j] > 1 then a[j] := j div a[j];
 
// Write the array to the console
nr_items := 0;
for j := 1 to limit do begin
Write( a[j]:5);
inc( nr_items);
if nr_items = items_per_line then begin
WriteLn;
nr_items := 0;
end;
end;
if nr_items > 0 then WriteLn;
end.
</syntaxhighlight>
{{out}}
<pre>
Largest proper divisors 1..100
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
</pre>
 
=={{header|Perl}}==
Line 2,185 ⟶ 2,351:
 
=={{header|Rust}}==
 
{{trans|Go}}
 
<syntaxhighlight lang="rust">
fn largest_proper_divisor(n: i32) -> i32 {
Line 2,192 ⟶ 2,361:
}
}
1
}
 
Line 2,226 ⟶ 2,394:
</pre>
 
 
{{trans|C}}
 
<syntaxhighlight lang="rust">
fn lpd(n: u32) -> u32 {
if n <= 1 {
1
} else {
(1..n).rev().find(|&i| n % i == 0).unwrap_or(1)
}
}
 
fn main() {
for i in 1..=100 {
print!("{:3}", lpd(i));
 
if i % 10 == 0 {
println!();
}
}
}
</syntaxhighlight>
 
{{out}}
<pre>
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
</pre>
 
=={{header|Ruby}}==
Line 2,295 ⟶ 2,499:
27 41 1 42 17 43 29 44 1 45
13 46 31 47 19 48 1 49 33 50
</pre>
 
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">1..100 -> map {|n| proper_divisors(n).tail \\ 1 }.slices(10).each {|a|
a.map{ '%3s' % _ }.join(' ').say
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
 
Line 2,471 ⟶ 2,693:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./math" for Int
import "./fmt" for Fmt
 
System.print("The largest proper divisors for numbers in the interval [1, 100] are:")
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/354839...354855"