Anonymous user
Smallest multiple: Difference between revisions
→{{header|Pascal}}: extended version
Thundergnat (talk | contribs) (→{{header|Raku}}: more concisely, use built-in) |
(→{{header|Pascal}}: extended version) |
||
Line 141:
<pre>
232792560
</pre>
===extended===
Find that the count of digits is nearly a constant x upper rangelimit.<br> The number of factors is the count of primes til limit.See GetFactorList.<br>No need for lcm or prime decomposition and other contortions.<BR>
Using prime sieve.
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI}
{$ELSE}
{$APPTAYPE CONSOLE}
{$ENDIF}
{$DEFINE USE_GMP}
uses
{$IFDEF USE_GMP}
gmp,
{$ENDIF}
sysutils; //format
const
UpperLimit = 2*1000*1000;
MAX_UINT64 = 46;
type
tFactors = array of Uint32;
tprimelist = array of byte;
var
primelist : tPrimelist;
procedure Init_Primes;
var
pPrime : pByte;
p ,i: NativeUInt;
begin
setlength(primelist,UpperLimit+3*8+1);
pPrime := @primelist[0];
//delete multiples of 2,3
i := 0;
repeat
//take care of endianess //0706050403020100
pUint64(@pPrime[i+0])^ := $0100010000000100;
pUint64(@pPrime[i+8])^ := $0000010001000000;
pUint64(@pPrime[i+16])^:= $0100000001000100;
inc(i,24);
until i>UpperLimit;
p := 5;
repeat
if pPrime[p] <> 0 then
begin
i := p*p;
if i > UpperLimit then
break;
repeat
pPrime[i] := 0;
inc(i,2*p);
until i>UpperLimit;
end;
inc(p,2);
until p*p>UpperLimit;
pPrime[1] := 0;
pPrime[2] := 1;
pPrime[3] := 1;
end;
{$IFDEF USE_GMP}
procedure ConvertToMPZ(const factors:tFactors);
var
mp : mpz_t;
s : AnsiString;
i : integer;
begin
mpz_init(mp);
mpz_set_ui(mp,1);
for i := 0 to high(factors) do
mpz_mul_ui(mp,mp,factors[i]);
i := mpz_sizeinbase(mp,10);
setlength(s,i+10);
mpz_get_str(@s[1],10,mp);
i := i+10;
while not(s[i] in['0'..'9']) do
dec(i);
setlength(s,i+1);
if length(s)> 22 then
begin
move(s[i-9],s[13],10);
s[11]:= '.';s[12]:= '.';
setlength(s,22);
end;
writeln(s);
mpz_clear(mp);
end;
{$ENDIF}
procedure CheckDigits(const factors:tFactors);
var
digCnt : extended;
i : integer;
begin
digcnt := 0;
for i := 0 to high(factors) do
digcnt += ln(factors[i]);
i := trunc(digcnt/ln(10)+1);
writeln(' has ',length(factors):10,' factors and ',i:10,' digits');
{$IFDEF USE_GMP}
If i < 10000 then
ConvertToMPZ(factors);
{$ENDIF}
end;
function ConvertToUint64(const factors:tFactors):Uint64;
var
i : integer;
begin
if length(factors) >15 then
Exit(0);
result := 1;
for i := 0 to high(factors) do
result *= factors[i];
end;
function ConvertToStr(const factors:tFactors):Ansistring;
var
s : Ansistring;
i : integer;
begin
result := '';
for i := 0 to high(factors)-1 do
begin
str(factors[i],s);
result += s+'*';
end;
str(factors[High(factors)],s);
result += s;
end;
procedure GetFactorList(var factors:tFactors;max:Uint32);
var
pPrime : pByte;
n,f,lf : Uint32;
BEGIN
pPrime := @primeList[0];
n := 2;
lf := 0;
setlength(factors,lf);
while n*n <= max do
Begin
if pPrime[n]<>0 then
begin
setlength(factors,lf+1);
f := n*n;
while f*n <= max do
f*= n;
factors[lf] := f;
inc(lf);
end;
inc(n);
end;
//the rest are all the primes up to max
For n := n to max do
if pPrime[n]<>0 then
Begin
setlength(factors,lf+1);
factors[lf] := n;
inc(lf);
end;
end;
procedure Check(var factors:tFactors;max:Uint32);
begin
GetFactorList(factors,max);
write(max:10,': ');
if length(factors)>15 then
CheckDigits(factors)
else
writeln(ConvertToUint64(factors):21,' = ',ConvertToStr(factors));
end;
var
factors:tFactors;
max: Uint32;
BEGIN
Init_Primes;
max := 200;
repeat
check(factors,max);
max *=10;
until max > UpperLimit;
For max := MAX_UINT64 downto 2 do
check(factors,max);
{$IFDEF WINDOWS}
READLN;
{$ENDIF}
END.</lang>
{{out}}
<pre style="height:300px">
TIO.RUN Real time: 0.203 s User time: 0.147 s Sys. time: 0.054 s CPU share: 98.88 %
200: has 46 factors and 90 digits
3372935888..0066992000
2000: has 303 factors and 867 digits
1511177948..5463680000
20000: has 2262 factors and 8676 digits
4879325627..8112000000
200000: has 17984 factors and 86871 digits
2000000: has 148933 factors and 868639 digits
46: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
45: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
44: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
43: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
42: 219060189739591200 = 32*27*25*7*11*13*17*19*23*29*31*37*41
41: 219060189739591200 = 32*27*25*7*11*13*17*19*23*29*31*37*41
40: 5342931457063200 = 32*27*25*7*11*13*17*19*23*29*31*37
39: 5342931457063200 = 32*27*25*7*11*13*17*19*23*29*31*37
38: 5342931457063200 = 32*27*25*7*11*13*17*19*23*29*31*37
37: 5342931457063200 = 32*27*25*7*11*13*17*19*23*29*31*37
36: 144403552893600 = 32*27*25*7*11*13*17*19*23*29*31
35: 144403552893600 = 32*27*25*7*11*13*17*19*23*29*31
34: 144403552893600 = 32*27*25*7*11*13*17*19*23*29*31
33: 144403552893600 = 32*27*25*7*11*13*17*19*23*29*31
32: 144403552893600 = 32*27*25*7*11*13*17*19*23*29*31
31: 72201776446800 = 16*27*25*7*11*13*17*19*23*29*31
30: 2329089562800 = 16*27*25*7*11*13*17*19*23*29
29: 2329089562800 = 16*27*25*7*11*13*17*19*23*29
28: 80313433200 = 16*27*25*7*11*13*17*19*23
27: 80313433200 = 16*27*25*7*11*13*17*19*23
26: 26771144400 = 16*9*25*7*11*13*17*19*23
25: 26771144400 = 16*9*25*7*11*13*17*19*23
24: 5354228880 = 16*9*5*7*11*13*17*19*23
23: 5354228880 = 16*9*5*7*11*13*17*19*23
22: 232792560 = 16*9*5*7*11*13*17*19
21: 232792560 = 16*9*5*7*11*13*17*19
20: 232792560 = 16*9*5*7*11*13*17*19
19: 232792560 = 16*9*5*7*11*13*17*19
18: 12252240 = 16*9*5*7*11*13*17
17: 12252240 = 16*9*5*7*11*13*17
16: 720720 = 16*9*5*7*11*13
15: 360360 = 8*9*5*7*11*13
14: 360360 = 8*9*5*7*11*13
13: 360360 = 8*9*5*7*11*13
12: 27720 = 8*9*5*7*11
11: 27720 = 8*9*5*7*11
10: 2520 = 8*9*5*7
9: 2520 = 8*9*5*7
8: 840 = 8*3*5*7
7: 420 = 4*3*5*7
6: 60 = 4*3*5
5: 60 = 4*3*5
4: 12 = 4*3
3: 6 = 2*3
2: 2 = 2
</pre>
| |||