Smallest multiple: Difference between revisions
Content added Content deleted
(→{{header|Pascal}}: extended version) |
Thundergnat (talk | contribs) m (Add related) |
||
| Line 2: | Line 2: | ||
;Task: |
;Task: |
||
Task |
Task description is taken from Project Euler |
||
<br>(https://projecteuler.net/problem=5) |
<br>(https://projecteuler.net/problem=5) |
||
<br>2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. |
<br>2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. |
||
<br>What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? |
<br>What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20? |
||
;Related |
|||
* [[Least common multiple]] |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{Trans|Wren}} |
{{Trans|Wren}} |
||
Revision as of 13:51, 21 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
Uses Algol 68G's LONG LONG INT which has specifiable precision.
<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
Go
<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
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
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 lcm or prime decomposition and other contortions.
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>
- Output:
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
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
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