Anonymous user
Practical numbers: Difference between revisions
m
→{{header|Pascal}}: shorten SumAllSetsForPractical even faster
m (→{{header|Pascal}}: renaming small modifications ( function to procedure )) |
m (→{{header|Pascal}}: shorten SumAllSetsForPractical even faster) |
||
Line 127:
</pre>
=={{header|Pascal}}==
simple brute force.Marking sum of divs by shifting the former sum by the the next divisor.<BR>
SumAllSetsForPractical tries to break as soon as possible.Should try to check versus [[wp:Practical number|https://en.wikipedia.org/wiki/Practical_number#Characterization_of_practical_numbers]]<BR>
<pre>
...σ denotes the sum of the divisors of x. For example, 2 × 3^2 × 29 × 823 = 429606 is practical,
because the inequality above holds for each of its prime factors:
3 ≤ σ(2) + 1 = 4, 29 ≤ σ(2 × 3^2) + 1 = 40, and 823 ≤ σ(2 × 3^2 × 29) + 1 = 1171. </pre>
<lang pascal>program practicalnumbers;
{$IFDEF FPC}
{$
{$ELSE}
{$APPTYPE CONSOLE}
Line 147 ⟶ 152:
Divs: tDivs;
HasSum :array of byte;
procedure GetDivisors(var Divs:tdivs;n:Uint32);
//calc all divisors,keep sorted
Line 192 ⟶ 196:
end;
function SumAllSetsForPractical(Limit:Uint32):boolean;
//mark sum and than shift by next divisor == add
//for practical numbers every sum must be marked
var
idx,j,loLimit,maxlimit,delta :
Begin
Limit := trunc(Limit*(Limit/Divs.DivsSumProp));
hs := @HasSum[0];▼
LoLimit:=0;
hs[0] := 1;//empty set▼
maxlimit := 0;
for idx := 0 to Divs.DivsMaxIdx do
Begin
delta := Divs.DivsVal[idx];
hs1 := @hs0[delta];
For j := maxlimit downto 0 do
maxlimit += delta;
while hs0[LoLimit]<> 0 do
//IF there is a 0 < delta, it will never be set
//IF there are more than the Limit set,
//it will be copied by the following Delta's
if (LoLimit < delta) OR (LoLimit > Limit) then
Break;
end;
end;
Line 227 ⟶ 241:
i := n-1;
sum := Divs.DivsSumProp;
if sum
result := false
else
Begin
IF length(HasSum) > sum+
else
Begin
setlength(HasSum,0);
setlength(HasSum,sum+8+1);
end;
▲ dec(i);
end;
▲ result := i<0;
end;
Line 283 ⟶ 295:
OutIsPractical(954432);
OutIsPractical(720);
OutIsPractical(5384);
OutIsPractical(1441440);
writeln(Divs.DivsNum,' has ',Divs.DivsMaxIdx+1,' proper divisors');
writeln((GetTickCount64-T0)/1000:10:3,' s');
T0 := GetTickCount64;
OutIsPractical(99998640);
writeln(Divs.DivsNum,' has ',Divs.DivsMaxIdx+1,' proper divisors ');
writeln((GetTickCount64-T0)/1000:10:3,' s');
T0 := GetTickCount64;
Line 294 ⟶ 311:
{{out}}
<pre> TIO.RUN.
1 2 4 6 8 12 16 18 20 24
28 30 32 36 40 42 48 54 56 60
Line 309 ⟶ 327:
954432 is not practical
720 is practical
5384 is not practical
1441440 is practical
1441440 has 287 proper divisors
0.
99998640 is not practical
99998640 has 119 proper divisors
0.200 s // with reserving memory
99998640 is not practical
99998640 has 119 proper divisors
Real time:
=={{header|Perl}}==
| |||