Practical numbers: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) (Added Perl) |
(added Pascal, simple brute force) |
||
Line 126: | Line 126: | ||
222222 is a practical number. |
222222 is a practical number. |
||
</pre> |
</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}}== |
=={{header|Perl}}== |