Anonymous user
Factors of an integer: Difference between revisions
→improvement: Thinking about Zumkeller numbers, where the most time comsuming part ist getting the factors.Now using prime decomposition and Calc factors .InsertSort faster than Quicksort (n = [1..1e6] 520ms -> 300 ms //Without sort 240
m (→optimized version: used a smaller font size for output, used a template for the output section.) |
(→improvement: Thinking about Zumkeller numbers, where the most time comsuming part ist getting the factors.Now using prime decomposition and Calc factors .InsertSort faster than Quicksort (n = [1..1e6] 520ms -> 300 ms //Without sort 240) |
||
Line 3,722:
</pre>
===
like [[http://rosettacode.org/wiki/Factors_of_an_integer#Prime_factoring C Prime_factoring]].<BR>
Insertion sort was much faster."runtime overhead" +25% instead +100% for quicksort against no sort.
{{works with|Free Pascal}}
<lang pascal>program
{$IFDEF FPC}
//{$R+,O+}
{$MODE DELPHI}
{$Optimization ON,ALL}
{$CodeAlign proc=8}
{$ELSE}
{$APPTYPE CONSOLE}
{$ENDIF}
uses
sysutils;
type
tPot = record
potPrim,
potMax :Uint32;
end;
tprimeFac = record
pfPrims : array[0..13] of tPot;
pfCnt,
pfFacCnt,
pfNum : Uint32;
end;
tSmallPrimes = array[0..6541] of Word;
tDivisors = array of Uint32;
tpDivisor = pUint32;
var
SmallPrimes: tSmallPrimes;
primeDecomp: tprimeFac;
Divisors : tDivisors;
procedure InsertSort(pDiv:tpDivisor; Left, Right : LongInt );
var
I, J: Int32;
Pivot : Uint32;
begin
for i:= 1 + Left to Right do
begin
Pivot:= pDiv[i];
j:= i - 1;
while (j >= Left) and (pDiv[j] > Pivot) do
begin
pDiv[j+1]:=pDiv[j];
Dec(j);
end;
pDiv[j+1]:= pivot;
end;
end;
procedure InitSmallPrimes;
var
pr,testPr,j,maxprimidx: Uint32;
isPrime : boolean;
Begin
maxprimidx := 0;
SmallPrimes[0] := 2;
pr := 3;
repeat
isprime := true;
j := 0;
repeat
testPr := SmallPrimes[j];
IF testPr*testPr > pr then
break;
If pr mod testPr = 0 then
Begin
isprime := false;
break;
end;
inc(j);
until false;
if isprime then
Begin
inc(maxprimidx);
SmallPrimes[maxprimidx]:= pr;
end;
inc(pr,2);
until pr > 1 shl 16 -1;
end;
procedure PrimeFacOut(primeDecomp:tprimeFac);
var
i : Uint32;
begin
with primeDecomp do
Begin
write(pfNum,' = ');
For i := 0 to pfCnt-2 do
with pfPrims[i] do
If potMax = 1 then
write(potPrim,'*')
else
write(potPrim,'^',potMax,'*');
with pfPrims[pfCnt-1] do
If potMax = 1 then
write(potPrim)
else
write(potPrim,'^',potMax);
end;
end;
function CntDivs(const primeDecomp:tprimeFac):NativeUint;inline;
begin
result := primeDecomp.pfFacCnt;
end;
procedure PrimeDecomposition(n:Uint32;var res:tprimeFac);
var
i,pr,cnt,cntFac,quot{to minimize divisions} : NativeUint;
Begin
res.pfNum := n;
cnt := 0;
i := 0;
repeat
quot := n div pr;
IF pr*quot
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := pr;
potMax := 0;
repeat
n := quot;
quot := quot div pr;
inc(potMax);
until pr*quot <> n;
cntFac *= (potMax+1);
end;
inc(Cnt);
end;
inc(i);
until false;
//a big prime left over?
IF n > 1 then
with res do
Begin
with pfPrims[Cnt] do
Begin
potPrim := n;
potMax := 1;
end;
cntFac *= 2;
inc(Cnt);
end;
res.pfCnt:= cnt;
res.pfFacCnt := cntFac;
end;
function GetDivSum(const primeDecomp:tprimeFac;var Divs:tDivisors):NativeUint;
var
pDivs : tpDivisor;
i,len,j,k,l,p,val: NativeInt;
Begin
i := CntDivs(primeDecomp);
IF i > Length(Divisors) then
setlength(Divisors,i);
pDivs := @Divs[0];
pDivs[0] := 1;
len := 1;
l := len;
result := 1;
For i := 0 to primeDecomp.pfCnt-1 do
with primeDecomp.pfPrims[i] do
Begin
//Multiply every divisor before with the new primefactors
//and append them to the list
p := potPrim;
val :=1;
k := potMax-1;
repeat
val *= p;
For j := 0 to len-1 do
Begin
pDivs[l]:= val*pDivs[j];
inc(l);
end;
dec(k);
until k<0;
len := l;
end;
//Sort. Insertsort much faster than QuickSort in this special case
InsertSort(pDivs,0,len-1);
end;
procedure AllFacsOut(n: Uint32);
var
k,j:Int32;
Begin
PrimeDecomposition(n,primeDecomp);
k := CntDivs(primeDecomp);
IF k > Length(Divisors) then
setlength(Divisors,k);
GetDivSum(primeDecomp,Divisors);
write(n:5,' got ',k:4,' divisors : ');
dec(k); // zero based
For j := 0 to k-1 do
write(Divisors[j],',');
writeln(Divisors[k]);
end;
var
number: Int32;
BEGIN
InitSmallPrimes;
setlength(Divisors,1);
writeln('Enter a number between 1 and 4294967295: ');
write('3491888400 is a nice choice ');
readln(number);
IF number > 1 then
AllFacsOut(number);
//https://en.wikipedia.org/wiki/Highly_composite_number <= HCN
//http://wwwhomes.uni-bielefeld.de/achim/highly.txt the first 1200 HCN
//AllFacsOut(3491888400);
END.</lang>
{{out}}
<pre>Enter a number between 1 and 4294967295:
3491888400 is a nice choice 120
120 got 16 divisors : 1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120
</pre>
=={{header|Perl}}==
| |||