Anonymous user
Smallest multiple: Difference between revisions
m
→extended: extended to show count of digits til 2 billion
(julia example) |
m (→extended: extended to show count of digits til 2 billion) |
||
Line 167:
</pre>
===extended===
Using prime sieve.
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI} {$Optimization On}
{$ELSE}
{$APPTAYPE CONSOLE}
Line 180:
{$ENDIF}
sysutils; //format
const
UpperLimit = MAX_LIMIT+1000;// so to find a prime beyond MAX_LIMIT
MAX_UINT64 = 46;// unused.Limit to get an Uint64 output
type
tFactors = array of Uint32;
tprimelist = array of byte;
var
factors,
saveFactors:tFactors;
saveFactorsIdx,
maxFactorsIdx : Uint32;
procedure Init_Primes;
var
pPrime : pByte;
p
begin
setlength(
pPrime := @
//delete multiples of 2,3
i := 0;
Line 206 ⟶ 209:
inc(i,24);
until i>UpperLimit;
cnt := 2;// 2,3
p := 5;
delta := 1;//5-3
repeat
if pPrime[p] <> 0 then
Line 213 ⟶ 218:
if i > UpperLimit then
break;
inc(cnt);
pPrime[p-2*delta] := delta;
delta := 0;
repeat
pPrime[i] := 0;
Line 219 ⟶ 227:
end;
inc(p,2);
inc(delta);
until p*p>UpperLimit;
setlength(saveFactors,cnt);
//convert to delta
repeat
if pPrime[p]<> 0 then
begin
pPrime[p-2*delta] := delta;
inc(cnt);
delta := 0;
end;
inc(p,2);
inc(delta);
until p > UpperLimit;
setlength(factors,cnt);
factors[0] := 2;
factors[1] := 3;
i := 2;
p := 5;
repeat
factors[i] := p;
p += 2*pPrime[p];
i += 1;
until i >= cnt;
setlength(primeDeltalist,0);
// writeln(length(savefactors)); writeln(length(factors));
end;
{$IFDEF USE_GMP}
procedure ConvertToMPZ(const factors:tFactors;dgtCnt:UInt32);
const
c19Digits = QWord(10*1000000)*1000000*1000000;
var
mp,mpdiv : mpz_t;
s : AnsiString;
f : Uint32;
i :int32;
begin
//Init and allocate space
mpz_init_set_ui(mp,0);
mpz_init(mpdiv);
mpz_ui_pow_ui(mpdiv,10,dgtCnt);
mpz_add(mp,mp,mpdiv);
mpz_add_ui(mp,mp,1);
mpz_set_ui(mp,1);
i := maxFactorsIdx;
repeat
last := rest;
rest *= f;
if rest div f <> last then
begin
mpz_mul_ui(mp,mp,last);
rest := f;
end;
dec(i);
until i < 0;
mpz_mul_ui(mp,mp,rest);
If dgtcnt>40 then
begin
rest := mpz_fdiv_ui(mp,c19Digits);
s
mpz_fdiv_q_ui (mpdiv,mpdiv,c19Digits);
mpz_fdiv_q(mp,mp,mpdiv);
rest := mpz_get_ui(mp);
writeln(rest:19,s);
mpz_clear(mpdiv);
end
else
Begin
setlength(s,dgtCnt+1000);
mpz_get_str(@s[1],10,mp);
writeln(s);
i := length(s);
while not(s[i] in['0'..'9']) do
dec(i);
setlength(s,i+1);
writeln(s);
end;
mpz_clear(mp);
end;
Line 256 ⟶ 316:
procedure CheckDigits(const factors:tFactors);
var
i : integer;
begin
repeat
inc(i);
until i > maxFactorsIdx;
dgtcnt := trunc(dgtcnt/ln(10))+1;
writeln(' has ',maxFactorsIdx+1:10,' factors and ',dgtcnt:10:0,' digits');
{$IFDEF USE_GMP}
if i < 1000*1000 then
ConvertToMPZ(factors,i);
{$ENDIF}
end;
Line 274 ⟶ 338:
i : integer;
begin
if
Exit(0);
result := 1;
for i := 0 to
result *= factors[i];
end;
Line 287 ⟶ 351:
begin
result := '';
for i := 0 to
begin
str(factors[i],s);
result += s+'*';
end;
str(factors[
result += s;
end;
Line 298 ⟶ 362:
procedure GetFactorList(var factors:tFactors;max:Uint32);
var
BEGIN
lf := 0;
saveFactors[lf] := p;
while p*p <= max do
Begin
while f*p <= max do
f
factors[lf] := f;
p := factors[lf]
if p=
end;
if lf>0 then
saveFactorsIdx := lf-1;
repeat
until
end;
procedure Check(var factors:tFactors;max:Uint32);
var
i: Uint32;
begin
GetFactorList(factors,max);
write(max:10,': ');
if
else
writeln(ConvertToUint64(factors):21,' = ',ConvertToStr(factors));
for i := 0 to saveFactorsIdx do
factors[i] := savefactors[i];
end;
var
max: Uint32;
BEGIN
Init_Primes;
max :=
repeat
check(factors,max);
max *=10;
until max >
writeln;
For max := 10 to 20 do // < MAX_UINT64
check(factors,max);
{$IFDEF WINDOWS}
READLN;
{$ENDIF}
END.
</lang>
{{out}}
<pre style="height:300px">
TIO.RUN Real time:
20: 232792560 = 16*9*5*7*11*13*17*19
200: has 46 factors and 90 digits
3372935888329262646..8060677390066992000
2000: has 303 factors and 867 digits
1511177948774443153..3786415805463680000
20000: has 2262 factors and 8676 digits
4879325627288270518..7411295098112000000
200000: has 17984 factors and 86871 digits
3942319728529926377..9513860925440000000
2000000: has 148933 factors and 868639 digits
8467191629995920178..6480233472000000000
{ at home
20000000: has 1270607 factors and 8686151 digits
1681437413936981958..6706037760000000000
200000000: has 11078937 factors and 86857606 digits
2000000000: has 98222287 factors and 868583388 digits
}
10: 2520 = 8*9*5*7
19: 232792560 = 16*9*5*7*11*13*17*19
20: 232792560 = 16*9*5*7*11*13*17*19
</pre>
|