Anonymous user
Practical numbers: Difference between revisions
added Pascal, simple brute force
SqrtNegInf (talk | contribs) (Added Perl) |
(added Pascal, simple brute force) |
||
Line 126:
222222 is a practical number.
</pre>
=={{header|Pascal}}==
simple brute force
<lang pascal>
program practicalnumbers;
{$IFDEF FPC}
{$MOde Delphi}
{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
type
tdivs = record
DivsVal : array[0..1920-1] of Uint32;
DivsMaxIdx :NativeInt;
end;
var
HasSum :array of byte;
function GetDivisors(n:NativeInt):tdivs;
var
i,ug,og:NativeInt;
Begin
ug := Low(tdivs.DivsVal);
og := High(tdivs.DivsVal);
i := 1;
while i*i < n do
begin
IF n mod i = 0 then
Begin
result.DivsVal[og] := n div i;
result.DivsVal[ug] := i;
dec(og);
inc(ug);
end;
inc(i);
end;
If i*i = n then
Begin
result.DivsVal[og] := i;
dec(og);
end;
while og < High(tDivs.DivsVal) do
begin
inc(og);
result.DivsVal[ug] := result.DivsVal[og];
inc(ug);
end;
result.DivsMaxIdx := ug-2;
end;
procedure SumUp(const Divs:tdivs;sum,i:UInt32);
Begin
if i>0 then
Begin
SumUp(Divs,sum,i-1);//don't sum this factor
SumUp(Divs,sum+Divs.DivsVal[i],i-1); //sum this factor
end
else
Begin
HasSum[sum] := 1;
HasSum[sum+1] := 1;//==sum+( DivsVal[0])=> )1
end;
end;
function isPractical(n:nativeInt):boolean;
//n must be > 1
var
Divs: tDivs;
i,sum:NativeInt;
Begin
Divs := GetDivisors(n);
sum := 0;
For i := Divs.DivsMaxIdx downto 0 do
sum += Divs.DivsVal[i];
i := n-1;
if sum >= i then
Begin
setlength(HasSum,sum+1);
SumUp(Divs,0,Divs.DivsMaxIdx);
while (i>= 0) AND (HasSum[i]<>0) do
dec(i);
setlength(HasSum,0);
end;
result := i<0;
end;
procedure OutIsPractical(n:nativeInt);
begin
If isPractical(n) then
writeln(n,' is practical')
else
writeln(n,' is not practical');
end;
var
n,cnt : NativeInt;
Begin
write(1:5);// extra
cnt := 9;
For n := 2 to 333 do
if isPractical(n) then
begin
write(n:5);
dec(cnt);
if cnt < 0 then
Begin
cnt := 10;
writeln;
end;
end;
writeln;
OutIsPractical(666);
OutIsPractical(6666);
OutIsPractical(66666);
OutIsPractical(720);
end.</lang>
{{out}}
<pre> TIO.RUN. 7 rows of 11 columns
1 2 4 6 8 12 16 18 20 24 28
30 32 36 40 42 48 54 56 60 64 66
72 78 80 84 88 90 96 100 104 108 112
120 126 128 132 140 144 150 156 160 162 168
176 180 192 196 198 200 204 208 210 216 220
224 228 234 240 252 256 260 264 270 272 276
280 288 294 300 304 306 308 312 320 324 330
666 is practical
6666 is practical
66666 is not practical
720 is practical
User time: 1.325 s CPU share: 99.19 %</pre>
=={{header|Perl}}==
| |||