Smallest multiple: Difference between revisions

From Rosetta Code
Content added Content deleted
(julia example)
m (→‎extended: extended to show count of digits til 2 billion)
Line 167: Line 167:
</pre>
</pre>
===extended===
===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>
fascinating 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 calculating lcm(lcm(lcm(1,2),3),4..) or prime decomposition<BR>
Using prime sieve.
Using prime sieve.
<lang pascal>{$IFDEF FPC}
<lang pascal>{$IFDEF FPC}
{$MODE DELPHI}
{$MODE DELPHI} {$Optimization On}
{$ELSE}
{$ELSE}
{$APPTAYPE CONSOLE}
{$APPTAYPE CONSOLE}
Line 180: Line 180:
{$ENDIF}
{$ENDIF}
sysutils; //format
sysutils; //format

const
const
UpperLimit = 2*1000*1000;
MAX_LIMIT = 2*1000*1000;
UpperLimit = MAX_LIMIT+1000;// so to find a prime beyond MAX_LIMIT
MAX_UINT64 = 46;
MAX_UINT64 = 46;// unused.Limit to get an Uint64 output
type
type
tFactors = array of Uint32;
tFactors = array of Uint32;
tprimelist = array of byte;
tprimelist = array of byte;
var
var
primelist : tPrimelist;
primeDeltalist : tPrimelist;
factors,

saveFactors:tFactors;
saveFactorsIdx,
maxFactorsIdx : Uint32;
procedure Init_Primes;
procedure Init_Primes;
var
var
pPrime : pByte;
pPrime : pByte;
p ,i: NativeUInt;
p,i,delta,cnt: NativeUInt;
begin
begin
setlength(primelist,UpperLimit+3*8+1);
setlength(primeDeltalist,UpperLimit+3*8+1);
pPrime := @primelist[0];
pPrime := @primeDeltalist[0];
//delete multiples of 2,3
//delete multiples of 2,3
i := 0;
i := 0;
Line 206: Line 209:
inc(i,24);
inc(i,24);
until i>UpperLimit;
until i>UpperLimit;
cnt := 2;// 2,3
p := 5;
p := 5;
delta := 1;//5-3
repeat
repeat
if pPrime[p] <> 0 then
if pPrime[p] <> 0 then
Line 213: Line 218:
if i > UpperLimit then
if i > UpperLimit then
break;
break;
inc(cnt);
pPrime[p-2*delta] := delta;
delta := 0;
repeat
repeat
pPrime[i] := 0;
pPrime[i] := 0;
Line 219: Line 227:
end;
end;
inc(p,2);
inc(p,2);
inc(delta);
until p*p>UpperLimit;
until p*p>UpperLimit;
setlength(saveFactors,cnt);
pPrime[1] := 0;
//convert to delta
pPrime[2] := 1;
repeat
pPrime[3] := 1;
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;
end;


{$IFDEF USE_GMP}
{$IFDEF USE_GMP}
procedure ConvertToMPZ(const factors:tFactors);
procedure ConvertToMPZ(const factors:tFactors;dgtCnt:UInt32);
const
c19Digits = QWord(10*1000000)*1000000*1000000;
var
var
mp : mpz_t;
mp,mpdiv : mpz_t;
s : AnsiString;
s : AnsiString;
i : integer;
rest,last : Uint64;
f : Uint32;
i :int32;
begin
begin
//Init and allocate space
mpz_init(mp);
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);
mpz_set_ui(mp,1);

for i := 0 to high(factors) do
i := maxFactorsIdx;
mpz_mul_ui(mp,mp,factors[i]);
i := mpz_sizeinbase(mp,10);
rest := 1;
repeat
setlength(s,i+10);
last := rest;
mpz_get_str(@s[1],10,mp);
i := i+10;
f := factors[i];
rest *= f;
while not(s[i] in['0'..'9']) do
if rest div f <> last then
begin
mpz_mul_ui(mp,mp,last);
rest := f;
end;
dec(i);
dec(i);
until i < 0;
setlength(s,i+1);
mpz_mul_ui(mp,mp,rest);
if length(s)> 22 then

If dgtcnt>40 then
begin
begin
rest := mpz_fdiv_ui(mp,c19Digits);
move(s[i-9],s[13],10);
s[11]:= '.';s[12]:= '.';
s := '..'+Format('%.19u',[rest]);
mpz_fdiv_q_ui (mpdiv,mpdiv,c19Digits);
setlength(s,22);
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;
end;
writeln(s);
mpz_clear(mp);
mpz_clear(mp);
end;
end;
Line 256: Line 316:
procedure CheckDigits(const factors:tFactors);
procedure CheckDigits(const factors:tFactors);
var
var
digCnt : extended;
dgtcnt : extended;
i : integer;
i : integer;
begin
begin
digcnt := 0;
dgtcnt := 0;
for i := 0 to high(factors) do
i := 0;
repeat
digcnt += ln(factors[i]);
i := trunc(digcnt/ln(10)+1);
dgtcnt += ln(factors[i]);
inc(i);
writeln(' has ',length(factors):10,' factors and ',i:10,' digits');
until i > maxFactorsIdx;
dgtcnt := trunc(dgtcnt/ln(10))+1;
writeln(' has ',maxFactorsIdx+1:10,' factors and ',dgtcnt:10:0,' digits');
{$IFDEF USE_GMP}
{$IFDEF USE_GMP}
If i < 10000 then
i := trunc(dgtcnt);
if i < 1000*1000 then
ConvertToMPZ(factors);
ConvertToMPZ(factors,i);
{$ENDIF}
{$ENDIF}
end;
end;
Line 274: Line 338:
i : integer;
i : integer;
begin
begin
if length(factors) >15 then
if maxFactorsIdx >15 then
Exit(0);
Exit(0);
result := 1;
result := 1;
for i := 0 to high(factors) do
for i := 0 to maxFactorsIdx do
result *= factors[i];
result *= factors[i];
end;
end;
Line 287: Line 351:
begin
begin
result := '';
result := '';
for i := 0 to high(factors)-1 do
for i := 0 to maxFactorsIdx-1 do
begin
begin
str(factors[i],s);
str(factors[i],s);
result += s+'*';
result += s+'*';
end;
end;
str(factors[High(factors)],s);
str(factors[maxFactorsIdx],s);
result += s;
result += s;
end;
end;
Line 298: Line 362:
procedure GetFactorList(var factors:tFactors;max:Uint32);
procedure GetFactorList(var factors:tFactors;max:Uint32);
var
var
pPrime : pByte;
p,f,lf : Uint32;
n,f,lf : Uint32;
BEGIN
BEGIN
pPrime := @primeList[0];
p := 2;
n := 2;
lf := 0;
lf := 0;
saveFactors[lf] := p;
setlength(factors,lf);
while p*p <= max do

while n*n <= max do
Begin
Begin
if pPrime[n]<>0 then
saveFactors[lf] := p;
begin
f := p*p;
while f*p <= max do
setlength(factors,lf+1);
f := n*n;
f*= p;
factors[lf] := f;
while f*n <= max do
f*= n;
inc(lf);
factors[lf] := f;
p := factors[lf];
inc(lf);
if p= 0 then HALT;
end;
inc(n);
end;
end;
if lf>0 then
//the rest are all the primes up to max
saveFactorsIdx := lf-1;
For n := n to max do
repeat
if pPrime[n]<>0 then
Begin
inc(lf)
setlength(factors,lf+1);
until factors[lf]>Max;
factors[lf] := n;
maxFactorsIdx := lf-1;
inc(lf);
end;
end;
end;


procedure Check(var factors:tFactors;max:Uint32);
procedure Check(var factors:tFactors;max:Uint32);
var
i: Uint32;
begin
begin
GetFactorList(factors,max);
GetFactorList(factors,max);
write(max:10,': ');
write(max:10,': ');
if length(factors)>15 then
if maxFactorsIdx>15 then
CheckDigits(factors)
CheckDigits(factors)
else
else
writeln(ConvertToUint64(factors):21,' = ',ConvertToStr(factors));
writeln(ConvertToUint64(factors):21,' = ',ConvertToStr(factors));
for i := 0 to saveFactorsIdx do
factors[i] := savefactors[i];
end;
end;


var
var
factors:tFactors;
max: Uint32;
max: Uint32;
BEGIN
BEGIN
Init_Primes;
Init_Primes;


max := 200;
max := 2;
repeat
repeat
check(factors,max);
check(factors,max);
max *=10;
max *=10;
until max > UpperLimit;
until max > MAX_LIMIT;

For max := MAX_UINT64 downto 2 do
writeln;
For max := 10 to 20 do // < MAX_UINT64
check(factors,max);
check(factors,max);
{$IFDEF WINDOWS}
{$IFDEF WINDOWS}
READLN;
READLN;
{$ENDIF}
{$ENDIF}
END.</lang>
END.
</lang>
{{out}}
{{out}}
<pre style="height:300px">
<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 %
TIO.RUN Real time: 1.161 s User time: 1.106 s Sys. time: 0.049 s CPU share: 99.49 %
200: has 46 factors and 90 digits
2: 2 = 2
20: 232792560 = 16*9*5*7*11*13*17*19
3372935888..0066992000
200: has 46 factors and 90 digits
3372935888329262646..8060677390066992000
2000: has 303 factors and 867 digits
2000: has 303 factors and 867 digits
1511177948774443153..3786415805463680000
1511177948..5463680000
20000: has 2262 factors and 8676 digits
20000: has 2262 factors and 8676 digits
4879325627288270518..7411295098112000000
4879325627..8112000000
200000: has 17984 factors and 86871 digits
200000: has 17984 factors and 86871 digits
3942319728529926377..9513860925440000000
2000000: has 148933 factors and 868639 digits
2000000: has 148933 factors and 868639 digits
8467191629995920178..6480233472000000000
46: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
{ at home
45: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
20000000: has 1270607 factors and 8686151 digits
44: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
1681437413936981958..6706037760000000000
43: 9419588158802421600 = 32*27*25*7*11*13*17*19*23*29*31*37*41*43
200000000: has 11078937 factors and 86857606 digits
42: 219060189739591200 = 32*27*25*7*11*13*17*19*23*29*31*37*41
2000000000: has 98222287 factors and 868583388 digits
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
10: 2520 = 8*9*5*7
9: 2520 = 8*9*5*7
11: 27720 = 8*9*5*7*11
8: 840 = 8*3*5*7
12: 27720 = 8*9*5*7*11
7: 420 = 4*3*5*7
13: 360360 = 8*9*5*7*11*13
6: 60 = 4*3*5
14: 360360 = 8*9*5*7*11*13
5: 60 = 4*3*5
15: 360360 = 8*9*5*7*11*13
4: 12 = 4*3
16: 720720 = 16*9*5*7*11*13
3: 6 = 2*3
17: 12252240 = 16*9*5*7*11*13*17
2: 2 = 2
18: 12252240 = 16*9*5*7*11*13*17
19: 232792560 = 16*9*5*7*11*13*17*19
20: 232792560 = 16*9*5*7*11*13*17*19
</pre>
</pre>


Revision as of 08:41, 22 October 2021

Smallest multiple is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Task

Task description is taken from Project Euler
(https://projecteuler.net/problem=5)
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Related


ALGOL 68

Translation of: Wren
Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

Uses Algol 68G's LONG LONG INT which has specifiable precision.

Library: ALGOL 68-primes

<lang algol68>BEGIN # find the smallest number that is divisible by each of the numbers 1..n # 

     # translation of the Wren sample #
   PR precision 1000 PR # set the precision of LONG LONG INT #
   PR read "primes.incl.a68" PR
   # returns the lowest common multiple of the numbers 1 : n #
   PROC lcm = ( INT n )LONG LONG INT:
        BEGIN
           # sieve the primes to n #
           []BOOL prime = PRIMESIEVE n;
           LONG LONG INT result := 1;
           FOR p TO UPB prime DO
               IF prime[ p ] THEN          
                   LONG LONG INT f := p;           # f will be set to the #
                   WHILE f * p <= n DO f *:= p OD; # highest multiple of p <= n #
                   result *:= f
               FI
           OD;
           result
        END # lcm # ;
   # returns a string representation of n with commas #
   PROC commatise = ( LONG LONG INT n )STRING:
        BEGIN
           STRING result      := "";
           STRING unformatted  = whole( n, 0 );
           INT    ch count    := 0;
           FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
               IF   ch count <= 2 THEN ch count +:= 1
               ELSE                    ch count  := 1; "," +=: result
               FI;
               unformatted[ c ] +=: result
           OD;
           result
        END; # commatise #
   print( ( "The LCMs of the numbers 1 to N inclusive is:", newline ) );
   []INT tests = ( 10, 20, 200, 2000 );
   FOR i FROM LWB tests TO UPB tests DO
       print( ( whole( tests[ i ], -5 ), ": ", commatise( lcm( tests[ i ] ) ), newline ) )
   OD

END</lang>

Output:
   10: 2,520
   20: 232,792,560
  200: 337,293,588,832,926,264,639,465,766,794,841,407,432,394,382,785,157,234,228,847,021,917,234,018,060,677,390,066,992,000
 2000: 151,117,794,877,444,315,307,536,308,337,572,822,173,736,308,853,579,339,903,227,904,473,000,476,322,347,234,655,122,160,866,668,946,941,993,951,014,270,933,512,030,194,957,221,371,956,828,843,521,568,082,173,786,251,242,333,157,830,450,435,623,211,664,308,500,316,844,478,617,809,101,158,220,672,108,895,053,508,829,266,120,497,031,742,749,376,045,929,890,296,052,805,527,212,315,382,805,219,353,316,270,742,572,401,962,035,464,878,235,703,759,464,796,806,075,131,056,520,079,836,955,770,415,021,318,508,272,982,103,736,658,633,390,411,347,759,000,563,271,226,062,182,345,964,184,167,346,918,225,243,856,348,794,013,355,418,404,695,826,256,911,622,054,015,423,611,375,261,945,905,974,225,257,659,010,379,414,787,547,681,984,112,941,581,325,198,396,634,685,659,217,861,208,771,400,322,507,388,161,967,513,719,166,366,839,894,214,040,787,733,471,287,845,629,833,993,885,413,462,225,294,548,785,581,641,804,620,417,256,563,685,280,586,511,301,918,399,010,451,347,815,776,570,842,790,738,545,306,707,750,937,624,267,501,103,840,324,470,083,425,714,138,183,905,657,667,736,579,430,274,197,734,179,172,691,637,931,540,695,631,396,056,193,786,415,805,463,680,000

Factor

Works with: Factor version 0.98

<lang factor>USING: math.functions math.ranges prettyprint sequences ;

20 [1,b] 1 [ lcm ] reduce .</lang>

Output:
232792560

Go

Translation of: Wren
Library: Go-rcu

<lang go>package main

import ( 

   "fmt"
   "math/big"
   "rcu"

)

func lcm(n int) *big.Int { 

   lcm := big.NewInt(1)
   t := new(big.Int)
   for _, p := range rcu.Primes(n) {
       f := p
       for f*p <= n {
           f *= p
       }
       lcm.Mul(lcm, t.SetUint64(uint64(f)))
   }
   return lcm

}

func main() { 

   fmt.Println("The LCMs of the numbers 1 to N inclusive is:")
   for _, i := range []int{10, 20, 200, 2000} {
       fmt.Printf("%4d: %s\n", i, lcm(i))
   }

}</lang>

Output:
The LCMs of the numbers 1 to N inclusive is:
  10: 2520
  20: 232792560
 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000
2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000

Julia

<lang julia>julia> foreach(x -> @show(lcm(x)), [1:10, 1:20, big"1":200, big"1":2000]) lcm(x) = 2520 lcm(x) = 232792560 lcm(x) = 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 lcm(x) = 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000 </lang>

Pascal

Here the simplest way, like Raku, check the highest exponent of every prime in range
Using harded coded primes. <lang pascal>{$IFDEF FPC} 

 {$MODE DELPHI}

{$ELSE} 

 {$APPTAYPE CONSOLE}

{$ENDIF} const 

smallprimes : array[0..10] of Uint32 = (2,3,5,7,11,13,17,19,23,29,31);
MAX = 20;

function getmaxfac(pr: Uint32): Uint32; //get the pr^highest exponent of prime used in 2 .. MAX var 

 i,fac : integer;

Begin 

 result := pr;
 while pr*result <= MAX do
   result *= pr;

end;

var 

 n,pr,prIdx : Uint32;

BEGIN 

 n := 1;
 prIdx := 0;
 pr := smallprimes[prIdx];
 repeat
   pr := smallprimes[prIdx];
   n *= getmaxfac(pr);
   inc(prIdx);
   pr := smallprimes[prIdx];
 until pr>MAX;
 writeln(n);

{$IFDEF WINDOWS} 

 READLN;

{$ENDIF} END. </lang>

Output:
  232792560

extended

fascinating find, that the count of digits is nearly a constant x upper rangelimit.
The number of factors is the count of primes til limit.See GetFactorList.
No need for calculating lcm(lcm(lcm(1,2),3),4..) or prime decomposition
Using prime sieve. <lang pascal>{$IFDEF FPC} 

 {$MODE DELPHI} {$Optimization On}

{$ELSE} 

 {$APPTAYPE CONSOLE}

{$ENDIF} {$DEFINE USE_GMP} uses 

 {$IFDEF USE_GMP}
 gmp,
 {$ENDIF}
 sysutils; //format

const 

 MAX_LIMIT = 2*1000*1000;
 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 

 primeDeltalist : tPrimelist;
 factors,
 saveFactors:tFactors;
 saveFactorsIdx,
 maxFactorsIdx : Uint32;

procedure Init_Primes; var 

 pPrime : pByte;
 p,i,delta,cnt: NativeUInt;

begin 

 setlength(primeDeltalist,UpperLimit+3*8+1);
 pPrime := @primeDeltalist[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;
 cnt := 2;// 2,3
 p := 5;
 delta := 1;//5-3
 repeat
   if pPrime[p] <> 0 then
   begin
     i := p*p;
     if i > UpperLimit then
       break;
     inc(cnt);
     pPrime[p-2*delta] := delta;
     delta := 0;
     repeat
       pPrime[i] := 0;
       inc(i,2*p);
     until i>UpperLimit;
   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;
 rest,last : Uint64;
 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;
 rest := 1;
 repeat
   last := rest;
   f := factors[i];
   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 := '..'+Format('%.19u',[rest]);
   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; {$ENDIF}

procedure CheckDigits(const factors:tFactors); var 

 dgtcnt : extended;
 i : integer;

begin 

 dgtcnt := 0;
 i := 0;
 repeat
   dgtcnt += ln(factors[i]);
   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}
   i := trunc(dgtcnt);
   if i < 1000*1000 then
     ConvertToMPZ(factors,i);
 {$ENDIF}

end;

function ConvertToUint64(const factors:tFactors):Uint64; var 

 i : integer;

begin 

 if maxFactorsIdx >15 then
   Exit(0);
 result := 1;
 for i := 0 to maxFactorsIdx do
   result *= factors[i];

end;

function ConvertToStr(const factors:tFactors):Ansistring; var 

 s : Ansistring;
 i : integer;

begin 

 result := ;
 for i := 0 to maxFactorsIdx-1 do
 begin
   str(factors[i],s);
   result += s+'*';
 end;
 str(factors[maxFactorsIdx],s);
 result += s;

end;

procedure GetFactorList(var factors:tFactors;max:Uint32); var 

 p,f,lf : Uint32;

BEGIN 

 p := 2;
 lf := 0;
 saveFactors[lf] := p;
 while p*p <= max do
 Begin
   saveFactors[lf] := p;
   f := p*p;
   while f*p <= max do
     f*= p;
   factors[lf] := f;
   inc(lf);
   p := factors[lf];
   if p= 0 then HALT;
 end;
 if lf>0 then
   saveFactorsIdx := lf-1;
 repeat
   inc(lf)
 until factors[lf]>Max;
 maxFactorsIdx := lf-1;

end;

procedure Check(var factors:tFactors;max:Uint32); var 

 i: Uint32;

begin 

 GetFactorList(factors,max);
 write(max:10,': ');
 if maxFactorsIdx>15 then
   CheckDigits(factors)
 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 := 2;
 repeat
   check(factors,max);
   max *=10;
 until max > MAX_LIMIT;

 writeln;
 For max := 10 to 20 do // < MAX_UINT64
   check(factors,max);

{$IFDEF WINDOWS} 

 READLN;

{$ENDIF} END. </lang>

Output:
TIO.RUN Real time: 1.161 s User time: 1.106 s Sys. time: 0.049 s CPU share: 99.49 %
         2:                     2 = 2
        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
        11:                 27720 = 8*9*5*7*11
        12:                 27720 = 8*9*5*7*11
        13:                360360 = 8*9*5*7*11*13
        14:                360360 = 8*9*5*7*11*13
        15:                360360 = 8*9*5*7*11*13
        16:                720720 = 16*9*5*7*11*13
        17:              12252240 = 16*9*5*7*11*13*17
        18:              12252240 = 16*9*5*7*11*13*17
        19:             232792560 = 16*9*5*7*11*13*17*19
        20:             232792560 = 16*9*5*7*11*13*17*19

Raku

Exercise with some larger values as well.

<lang perl6>say "$_: ", [lcm] 2..$_ for <10 20 200 2000></lang>

Output:
10: 2520
20: 232792560
200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000
2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000

Ring

<lang ring> see "working..." + nl see "Smallest multiple is:" + nl n = 0

while true 

     n++
     flag = 0
     for m = 1 to 20
         if n % m = 0
            flag += 1
         ok
     next
     if flag = 20
        see "" + n + nl
        exit
     ok

end

see "done..." + nl </lang>

Output:
working...
Smallest multiple is:
232792560
done...

Wren

Library: Wren-math
Library: Wren-big
Library: Wren-fmt


We don't really need a computer for the task as set because it's just the product of the maximum prime powers <= 20 which is : 16 x 9 x 5 x 7 x 11 x 13 x 17 x 19 = 232,792,560.

More formally and quite quick by Wren standards at 0.017 seconds: <lang ecmascript>import "./math" for Int import "./big" for BigInt import "./fmt" for Fmt

var lcm = Fn.new { |n| 

   var primes = Int.primeSieve(n)
   var lcm = BigInt.one
   for (p in primes) {
       var f = p
       while (f * p <= n) f = f * p
       lcm = lcm * f
   }
   return lcm

}

System.print("The LCMs of the numbers 1 to N inclusive is:") for (i in [10, 20, 200, 2000]) Fmt.print("$,5d: $,i", i, lcm.call(i))</lang>

Output:
The LCMs of the numbers 1 to N inclusive is:
   10: 2,520
   20: 232,792,560
  200: 337,293,588,832,926,264,639,465,766,794,841,407,432,394,382,785,157,234,228,847,021,917,234,018,060,677,390,066,992,000
2,000: 151,117,794,877,444,315,307,536,308,337,572,822,173,736,308,853,579,339,903,227,904,473,000,476,322,347,234,655,122,160,866,668,946,941,993,951,014,270,933,512,030,194,957,221,371,956,828,843,521,568,082,173,786,251,242,333,157,830,450,435,623,211,664,308,500,316,844,478,617,809,101,158,220,672,108,895,053,508,829,266,120,497,031,742,749,376,045,929,890,296,052,805,527,212,315,382,805,219,353,316,270,742,572,401,962,035,464,878,235,703,759,464,796,806,075,131,056,520,079,836,955,770,415,021,318,508,272,982,103,736,658,633,390,411,347,759,000,563,271,226,062,182,345,964,184,167,346,918,225,243,856,348,794,013,355,418,404,695,826,256,911,622,054,015,423,611,375,261,945,905,974,225,257,659,010,379,414,787,547,681,984,112,941,581,325,198,396,634,685,659,217,861,208,771,400,322,507,388,161,967,513,719,166,366,839,894,214,040,787,733,471,287,845,629,833,993,885,413,462,225,294,548,785,581,641,804,620,417,256,563,685,280,586,511,301,918,399,010,451,347,815,776,570,842,790,738,545,306,707,750,937,624,267,501,103,840,324,470,083,425,714,138,183,905,657,667,736,579,430,274,197,734,179,172,691,637,931,540,695,631,396,056,193,786,415,805,463,680,000
Retrieved from "https://rosettacode.org/wiki/Smallest_multiple?oldid=316513"