Anonymous user
Practical numbers: Difference between revisions
→{{header|Pascal}}: Now without generating sum of allset
m (→{{header|Pascal}}: shorten SumAllSetsForPractical even faster) |
(→{{header|Pascal}}: Now without generating sum of allset) |
||
Line 339:
Real time: 0.506 s CPU share: 87.94 %</pre>
==={{header|alternative}}===
Now without generating sum of allset.
<lang pascal>program practicalnumbers;
{$IFDEF FPC}
{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
type
tdivs = record
DivsVal : array[0..2048-1] of Uint32;
end;
var
Divs: tDivs;
function CheckIsPractical(var Divs:tdivs;n:Uint32):boolean;
//calc all divisors,calc sum of divisors
var
i,quot,ug,og : UInt32;
sum: UInt64;
Begin
with Divs do
Begin
sum := 0;
ug := Low(tdivs.DivsVal);
og := High(tdivs.DivsVal);
i := 1;
while i*i < n do
begin
quot := n div i;
IF n - quot*i = 0 then
Begin
if sum+1 < i then
EXIT(FALSE);
DivsVal[og] := quot;
DivsVal[ug] := i;
inc(sum,i);
dec(og);
inc(ug);
end;
inc(i);
end;
If i*i = n then
Begin
if sum+1 < i then
if sum+1 < i then
EXIT(FALSE);
DivsVal[og] := i;
inc(sum,i);
dec(og);
end;
//check higher
while og < High(tDivs.DivsVal) do
begin
inc(og);
i := DivsVal[og];
if sum+1 < i then
EXIT(FALSE);
inc(sum,i);
If sum>=n-1 then
EXIT(TRUE);
end;
end;//with
end;
function isPractical(n:Uint32):boolean;
Begin
if n= 1 then
EXIT(True);
if ODD(n) then
EXIT(false);
result:=CheckIsPractical(Divs,n);
end;
procedure OutIsPractical(n:nativeInt);
begin
If isPractical(n) then
writeln(n,' is practical')
else
writeln(n,' is not practical');
end;
const
ColCnt = 10;
MAX = 333;
var
T0 : INt64;
n,col,count : NativeInt;
Begin
col:=ColCnt;
count := 0;
For n := 1 to MAX do
if isPractical(n) then
begin
write(n:5);
inc(count);
dec(col);
if col = 0 then
Begin
writeln;
col :=ColCnt;
end;
end;
writeln;
writeln('There are ',count,' pratical numbers from 1 to ',MAX);
writeln;
T0 := GetTickCount64;
OutIsPractical(666);
OutIsPractical(6666);
OutIsPractical(66666);
OutIsPractical(954432);
OutIsPractical(720);
OutIsPractical(5384);
OutIsPractical(1441440);
OutIsPractical(99998640);
Writeln( (GetTickCount64- T0)/1000:7:5,' s');
{$IFDEF WINDOWS} readln;{$ENDIF}
end.</lang>
{{out}}
<pre> TIO.RUN
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
There are 77 pratical numbers from 1 to 333
666 is practical
6666 is practical
66666 is not practical
954432 is not practical
720 is practical
5384 is not practical
1441440 is practical
99998640 is not practical
0.00000 s</pre>
=={{header|Perl}}==
| |||