Smallest multiple: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) (→{{header|Raku}}: more concisely, use built-in) |
(→{{header|Pascal}}: extended version) |
||
Line 141: | Line 141: | ||
<pre> |
<pre> |
||
232792560 |
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> |
</pre> |
||