Largest proper divisor of n: Difference between revisions
Content added Content deleted
(Added alternative solution for Pascal) |
|||
Line 1,808: | Line 1,808: | ||
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> |
||
===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}}== |
=={{header|Perl}}== |