Anonymous user
Factors of an integer: Difference between revisions
m
→using Prime decomposition: using TIO.RUN .delete text accidently inserted by middle mouse click
(→using Prime decomposition: updated from zumkeller numbers. Fast for consecutive integers.) |
m (→using Prime decomposition: using TIO.RUN .delete text accidently inserted by middle mouse click) |
||
Line 4,281:
//HCN(86) > 1.2E11 = 128,501,493,120 count of divs = 4096 7 3 1 1 1 1 1 1 1
HCN_DivCnt = 4096;
type
tItem = Uint64;
tDivisors = array [0..HCN_DivCnt
tpDivisor = pUint64;
const
//used odd size for test only
SizePrDeFe =
type
tdigits = array [0..31] of Uint32;
//the first number with 11 different
//
//56 byte
tprimeFac = packed record
pfSumOfDivs,
pfRemain : Uint64;
end;
tpPrimeFac = ^tprimeFac;
Line 4,307:
var
{$ALIGN 8}
SmallPrimes: tPrimes;
{$ALIGN 32}
PrimeDecompField :tPrimeDecompField;
pdfIDX,pdfOfs: NativeInt;
procedure InitSmallPrimes;
//get primes.
const
MAXLIMIT = (821641-1) shr 1;
Line 4,352 ⟶ 4,354:
flipflop := 3-flipflop;
until (p > MAXLIMIT) OR (j>High(SmallPrimes));
end;
function OutPots(pD:tpPrimeFac;n:NativeInt):Ansistring;
Line 4,372:
if n>0 then
result += '*';
p :=
chk *= p;
str(p,s);
Line 4,401:
end;
end;
function smplPrimeDecomp(n:Uint64):tprimeFac;
var
Line 4,411 ⟶ 4,412:
pfRemain := n;
pfMaxIdx := 0;
pfpotMax[0] := 0;
begin▼
pot := BsfQWord(n);▼
pfMaxIdx := 1;▼
n := n shr pot;▼
end;▼
i := 1;▼
while i < High(SmallPrimes) do
begin
pr := SmallPrimes[i];
q := n DIV pr;
//if n < pr*pr
if pr > q then
BREAK;
if n = pr*q then
Begin
pot := 0;
fac := pr;
Line 4,461 ⟶ 4,451:
function CnvtoBASE(var dgt:tDigits;n:Uint64;base:NativeUint):NativeInt;
//n must be multiple of base aka n mod base must be 0
var
q,r: Uint64;
Line 4,468 ⟶ 4,458:
fillchar(dgt,SizeOf(dgt),#0);
i := 0;
n := n div base;
result := 0;
Line 4,479 ⟶ 4,468:
inc(i);
until (q = 0);
//searching lowest pot in base
result := 0;
while (result<i) AND (dgt[result] = 0) do
Line 4,502 ⟶ 4,491:
end;
var
dgt:tDigits;
i,
begin
n := pdfOfs;
EXIT(FALSE);
//init
for i := 0 to SizePrDeFe-1 do
Line 4,517 ⟶ 4,508:
pfRemain := n+i;
pfMaxIdx := 0;
pfpotMax[0] := 0;
end;
end;
//first factor 2. Make n+i even
i := (pdfIdx+n) AND 1;
IF (n = 0) AND (pdfIdx<2) then
Line 4,532 ⟶ 4,522:
j := BsfQWord(n+i);
pfMaxIdx := 1;
pfpotMax[0] := j;
pfRemain := (n+i) shr j;
Line 4,540 ⟶ 4,530:
i += 2;
until i >=SizePrDeFe;
//
i := 0;
maxP := trunc(sqrt(n+SizePrDeFe))+1;
repeat
//search next prime that is in bounds of sieve
repeat
if i >= High(SmallPrimes) then▼
pr := SmallPrimes[i];
k := pr-n MOD pr;
▲ begin
▲ if i >= High(SmallPrimes) then
if (k = pr) AND (n>0) then
if k < SizePrDeFe then
break;
until pr > MaxP;
▲ end;
//no need to use higher primes
if pr*pr > n+SizePrDeFe then
BREAK;
//
j := CnvtoBASE(dgt,n+k,pr);
repeat
with pdf[k] do
Begin
pfpotMax[pfMaxIdx] := j;
pfDivCnt *= j+1;
Line 4,596 ⟶ 4,597:
end;
end;
result := true;
end;
begin
dec(pdfIDX,SizePrDeFe);
inc(pdfOfs,SizePrDeFe);
result := SieveOneSieve(PrimeDecompField);
end;
Line 4,608 ⟶ 4,610:
begin
if pdfIDX >= SizePrDeFe then
if Not(NextSieve
EXIT(NIL);
result := @PrimeDecompField[pdfIDX];
inc(pdfIDX);
end;
//Init Sieve pdfIdx,pdfOfs are Global
begin
pdfIdx := n MOD SizePrDeFe;
pdfOfs := n-pdfIdx;
result := SieveOneSieve(PrimeDecompField);
end;
Line 4,645 ⟶ 4,648:
i,len,j,l,p,k: Int32;
Begin
pDivs := @Divs[0];
pDivs[0] := 1;
Line 4,657 ⟶ 4,659:
//and append them to the list
k := pfpotMax[i];
p :=
pPot :=1;
repeat
Line 4,683 ⟶ 4,685:
//Sort. Insertsort much faster than QuickSort in this special case
InsertSort(pDivs,0,len-1);
//end marker
pDivs[len] :=0;
end;
procedure AllFacsOut(
var
k,j: Int32;
Begin
k :=
if Proper
repeat
IF
write(Divs[k],',');
inc(j);
inc(k);
until false;
writeln(Divs[k]);
end;
Line 4,709 ⟶ 4,718:
T0 := GetTickCount64;
n := 0;
Init_Sieve(0);
repeat
pPrimeDecomp:= GetNextPrimeDecomp;
inc(n);
until n > 10*1000*1000+1;
Line 4,719 ⟶ 4,727:
writeln('runtime ',T0/1000:0:3,' s');
GetDivisors(pPrimeDecomp,Divs);
AllFacsOut(
AllFacsOut(
writeln('simple version');
T0 := GetTickCount64;
n := 0;
repeat
Mypd:= smplPrimeDecomp(n);
inc(n);
until n > 10*1000*1000+1;
Line 4,747 ⟶ 4,740:
writeln('runtime ',T0/1000:0:3,' s');
GetDivisors(@Mypd,Divs);
AllFacsOut(
AllFacsOut(
end.</lang>
</lang>▼
{{out}}
<pre>
TIO.RUN
runtime 1.216 s▼
//out-commented GetDivisors, but still calculates sum of divisors and count of divisors▼
1,11,909091
1,11,909091,10000001
simple version
runtime
1,11,909091
1,11,909091,10000001
Real time: 8.868 s CPU share: 99.57 %
//with GetDivisors
▲//out-commented GetDivisors, but still calculates sum of divisors and count of divisors
▲runtime 0.311 s
1,11,909091
1,11,909091,10000001
simple version
runtime
1,11,909091
1,11,909091,10000001
Real time: 13.082 s CPU share: 99.16 %
=={{header|Perl}}==
|