Practical numbers: Difference between revisions
Content added Content deleted
m (→{{header|Pascal}}: shorten SumAllSetsForPractical even faster) |
(→{{header|Pascal}}: Now without generating sum of allset) |
||
Line 339: | Line 339: | ||
Real time: 0.506 s CPU share: 87.94 %</pre> |
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}}== |
=={{header|Perl}}== |