Smallest multiple: Difference between revisions
(Smallest multiple in Verilog) |
(Added Easylang) |
||
(12 intermediate revisions by 10 users not shown) | |||
Line 13: | Line 13: | ||
=={{header|11l}}== |
=={{header|11l}}== |
||
< |
<syntaxhighlight lang="11l">F f(n) |
||
V ans = BigInt(1) |
V ans = BigInt(1) |
||
L(i) 1..n |
L(i) 1..n |
||
Line 20: | Line 20: | ||
L(n) [10, 20, 200, 2000] |
L(n) [10, 20, 200, 2000] |
||
print(n‘: ’f(n))</ |
print(n‘: ’f(n))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 35: | Line 35: | ||
Uses Algol 68G's LONG LONG INT which has specifiable precision. |
Uses Algol 68G's LONG LONG INT which has specifiable precision. |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # find the smallest number that is divisible by each of the numbers 1..n # |
||
# translation of the Wren sample # |
# translation of the Wren sample # |
||
PR precision 1000 PR # set the precision of LONG LONG INT # |
PR precision 1000 PR # set the precision of LONG LONG INT # |
||
Line 73: | Line 73: | ||
print( ( whole( tests[ i ], -5 ), ": ", commatise( lcm( tests[ i ] ) ), newline ) ) |
print( ( whole( tests[ i ], -5 ), ": ", commatise( lcm( tests[ i ] ) ), newline ) ) |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 81: | Line 81: | ||
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 |
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 |
||
</pre> |
</pre> |
||
=={{header|Arturo}}== |
|||
<syntaxhighlight lang="arturo">print first select.first range.step:20 20 ∞ 'x -> |
|||
every? 11..19 'z -> zero? x % z</syntaxhighlight> |
|||
{{out}} |
|||
<pre>232792560</pre> |
|||
=={{header|Asymptote}}== |
|||
<syntaxhighlight lang="asymptote">int temp = 2*3*5*7*11*13*17*19; |
|||
int smalmul = temp; |
|||
int lim = 1; |
|||
while (lim <= 20) { |
|||
lim = lim + 1; |
|||
while (smalmul % lim != 0) { |
|||
lim = 1; |
|||
smalmul = smalmul + temp; |
|||
} |
|||
} |
|||
write(smalmul);</syntaxhighlight> |
|||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">primes := 1 |
||
loop 20 |
loop 20 |
||
if prime_numbers(A_Index).Count() = 1 |
if prime_numbers(A_Index).Count() = 1 |
||
Line 132: | Line 154: | ||
ans.push(n) |
ans.push(n) |
||
return ans |
return ans |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>232792560</pre> |
<pre>232792560</pre> |
||
=={{header|BASIC}}== |
|||
==={{header|BASIC256}}=== |
|||
<syntaxhighlight lang="freebasic">temp = 2*3*5*7*11*13*17*19 |
|||
smalmul = temp |
|||
lim = 1 |
|||
do |
|||
lim += 1 |
|||
if (smalmul mod lim) then lim = 1 : smalmul += temp |
|||
until lim = 20 |
|||
print smalmul</syntaxhighlight> |
|||
{{out}} |
|||
<pre>232792560</pre> |
|||
==={{header|PureBasic}}=== |
|||
<syntaxhighlight lang="purebasic">OpenConsole() |
|||
temp.i = 2*3*5*7*11*13*17*19 |
|||
smalmul.i = temp |
|||
lim.i = 1 |
|||
Repeat |
|||
lim + 1 |
|||
If (smalmul % lim) |
|||
lim = 1 |
|||
smalmul = smalmul + temp |
|||
EndIf |
|||
Until lim = 20 |
|||
PrintN(Str(smalmul)) |
|||
Input() |
|||
CloseConsole()</syntaxhighlight> |
|||
{{out}} |
|||
<pre>232792560</pre> |
|||
==={{header|True BASIC}}=== |
|||
<syntaxhighlight lang="qbasic">LET temp = 2*3*5*7*11*13*17*19 |
|||
LET smalmul = temp |
|||
LET lim = 1 |
|||
DO |
|||
LET lim = lim+1 |
|||
IF (REMAINDER(ROUND(smalmul),ROUND(lim)) <> 0) THEN |
|||
LET lim = 1 |
|||
LET smalmul = smalmul+temp |
|||
END IF |
|||
LOOP UNTIL lim = 20 |
|||
PRINT smalmul |
|||
END</syntaxhighlight> |
|||
{{out}} |
|||
<pre>232792560</pre> |
|||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function IsDivisible120(N: integer): boolean; |
|||
{Is N evenly divisible by numbers 1..20} |
|||
var I: integer; |
|||
begin |
|||
Result:=False; |
|||
{For speed - larger numbers less likely divisor} |
|||
for I:=20 downto 2 do |
|||
if (N mod I)<>0 then exit; |
|||
Result:=True; |
|||
end; |
|||
procedure SmallestDivide120(Memo: TMemo); |
|||
var I: integer; |
|||
begin |
|||
{Only look at even numbers for speed} |
|||
for I:=1 to High(Integer) do |
|||
if IsDivisible120(I*2) then |
|||
begin |
|||
Memo.Lines.Add(FloatToStrF(I*2,ffNumber,18,0)); |
|||
break; |
|||
end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
232,792,560 |
|||
Elapsed Time: 920.406 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
{{trans|Wren}} |
|||
<syntaxhighlight> |
|||
fastfunc isprim num . |
|||
i = 2 |
|||
while i <= sqrt num |
|||
if num mod i = 0 |
|||
return 0 |
|||
. |
|||
i += 1 |
|||
. |
|||
return 1 |
|||
. |
|||
n = 20 |
|||
res = 1 |
|||
for p = 2 to n |
|||
if isprim p = 1 |
|||
f = p |
|||
while f * p <= n |
|||
f = f * p |
|||
. |
|||
res *= f |
|||
. |
|||
. |
|||
print res |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
232792560 |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Least Multiple. Nigel Galloway: October 22nd., 2021 |
// Least Multiple. Nigel Galloway: October 22nd., 2021 |
||
let fG n g=let rec fN i=match i*g with g when n>g->fN g |_->i in fN g |
let fG n g=let rec fN i=match i*g with g when n>g->fN g |_->i in fN g |
||
let leastMult n=let fG=fG n in primes32()|>Seq.takeWhile((>=)n)|>Seq.map fG|>Seq.reduce((*)) |
let leastMult n=let fG=fG n in primes32()|>Seq.takeWhile((>=)n)|>Seq.map fG|>Seq.reduce((*)) |
||
printfn $"%d{leastMult 20}" |
printfn $"%d{leastMult 20}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
232792560 |
232792560 |
||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
< |
<syntaxhighlight lang="factor">USING: math.functions math.ranges prettyprint sequences ; |
||
20 [1,b] 1 [ lcm ] reduce .</ |
20 [1,b] 1 [ lcm ] reduce .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 159: | Line 300: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">Func Ilog( n, b ) = |
||
i:=0; {integer logarithm of n to base b, positive only} |
i:=0; {integer logarithm of n to base b, positive only} |
||
while b^i<=n do |
while b^i<=n do |
||
Line 174: | Line 315: | ||
!Smalmul(20); |
!Smalmul(20); |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>232792560</pre> |
{{out}}<pre>232792560</pre> |
||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
Use the code from the [[Least common multiple]] example as an include. |
Use the code from the [[Least common multiple]] example as an include. |
||
< |
<syntaxhighlight lang="freebasic">#include"lcm.bas" |
||
redim shared as ulongint smalls(0 to 1) 'calculate and store as we go |
redim shared as ulongint smalls(0 to 1) 'calculate and store as we go |
||
Line 198: | Line 339: | ||
for i as uinteger = 0 to 20 |
for i as uinteger = 0 to 20 |
||
print i, smalmul(i) |
print i, smalmul(i) |
||
next i</ |
next i</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 229: | Line 370: | ||
fmt.Printf("%4d: %s\n", i, lcm(i)) |
fmt.Printf("%4d: %s\n", i, lcm(i)) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 241: | Line 382: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Text.Printf (printf) |
||
--- SMALLEST INTEGER EVENLY DIVISIBLE BY EACH OF [1..N] -- |
--- SMALLEST INTEGER EVENLY DIVISIBLE BY EACH OF [1..N] -- |
||
Line 260: | Line 401: | ||
showSmallest = |
showSmallest = |
||
((<>) . (<> " -> ") . printf "%4d") |
((<>) . (<> " -> ") . printf "%4d") |
||
<*> (printf "%d" . smallest)</ |
<*> (printf "%d" . smallest)</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre> 10 -> 2520 |
<pre> 10 -> 2520 |
||
Line 266: | Line 407: | ||
200 -> 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
200 -> 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
||
2000 -> 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000</pre> |
2000 -> 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000</pre> |
||
=={{header|J}}== |
|||
<syntaxhighlight lang="j"> *./ >: i. 20 |
|||
232792560</syntaxhighlight> |
|||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 275: | Line 420: | ||
(*) The C implementation of jq has sufficient accuracy for N == 20 but not N == 200, |
(*) The C implementation of jq has sufficient accuracy for N == 20 but not N == 200, |
||
so the output shown below is based on a run of gojq. |
so the output shown below is based on a run of gojq. |
||
< |
<syntaxhighlight lang="jq"># Output: a stream of primes less than $n in increasing order |
||
def primes($n): |
def primes($n): |
||
2, (range(3; $n; 2) | select(is_prime)); |
2, (range(3; $n; 2) | select(is_prime)); |
||
Line 287: | Line 432: | ||
"N: LCM of the numbers 1 to N inclusive", |
"N: LCM of the numbers 1 to N inclusive", |
||
( 10, 20, 200, 2000 |
( 10, 20, 200, 2000 |
||
| "\(.): \(smallest_multiple)" )</ |
| "\(.): \(smallest_multiple)" )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 298: | Line 443: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">julia> foreach(x -> @show(lcm(x)), [1:10, 1:20, big"1":200, big"1":2000]) |
||
lcm(x) = 2520 |
lcm(x) = 2520 |
||
lcm(x) = 232792560 |
lcm(x) = 232792560 |
||
lcm(x) = 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
lcm(x) = 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
||
lcm(x) = 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000 |
lcm(x) = 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
<lang |
<syntaxhighlight lang="mathematica">LCM @@ Range[20]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
232792560 |
232792560 |
||
</pre> |
</pre> |
||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let rec gcd a = function |
|||
| 0 -> a |
|||
| b -> gcd b (a mod b) |
|||
let lcm a b = |
|||
a * b / gcd a b |
|||
let smallest_multiple n = |
|||
Seq.(ints 1 |> take n |> fold_left lcm 1) |
|||
let () = |
|||
Printf.printf "%u\n" (smallest_multiple 20)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>232792560</pre> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
Here the simplest way, like Raku, check the highest exponent of every prime in range<BR> |
Here the simplest way, like Raku, check the highest exponent of every prime in range<BR> |
||
Using harded coded primes. |
Using harded coded primes. |
||
< |
<syntaxhighlight lang="pascal">{$IFDEF FPC} |
||
{$MODE DELPHI} |
{$MODE DELPHI} |
||
{$ELSE} |
{$ELSE} |
||
Line 350: | Line 512: | ||
{$ENDIF} |
{$ENDIF} |
||
END. |
END. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 358: | Line 520: | ||
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> |
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. |
||
< |
<syntaxhighlight lang="pascal">{$IFDEF FPC} |
||
{$MODE DELPHI} {$Optimization On} |
{$MODE DELPHI} {$Optimization On} |
||
{$ELSE} |
{$ELSE} |
||
Line 607: | Line 769: | ||
{$ENDIF} |
{$ENDIF} |
||
END. |
END. |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre style="height:300px"> |
<pre style="height:300px"> |
||
Line 643: | Line 805: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Smallest_multiple#Raku |
use strict; # https://rosettacode.org/wiki/Smallest_multiple#Raku |
||
Line 649: | Line 811: | ||
use ntheory qw( lcm ); |
use ntheory qw( lcm ); |
||
print "for $_, it's @{[ lcm(1 .. $_) ]}\n" for 10, 20;</ |
print "for $_, it's @{[ lcm(1 .. $_) ]}\n" for 10, 20;</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 655: | Line 817: | ||
for 20, it's 232792560 |
for 20, it's 232792560 |
||
</pre> |
</pre> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
Using the builtin, limited to 2<small><sup>53</sup></small> aka N=36 on 32-bit, 2<small><sup>64</sup></small> aka N=46 on 64-bit. |
Using the builtin, limited to 2<small><sup>53</sup></small> aka N=36 on 32-bit, 2<small><sup>64</sup></small> aka N=46 on 64-bit. |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">))</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">20</span><span style="color: #0000FF;">))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 669: | Line 830: | ||
Using gmp |
Using gmp |
||
{{trans|Wren}} |
{{trans|Wren}} |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
||
Line 685: | Line 846: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The LCMs of the numbers 1 to N inclusive is:\n"</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The LCMs of the numbers 1 to N inclusive is:\n"</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2000</span><span style="color: #0000FF;">},</span><span style="color: #000000;">plcmz</span><span style="color: #0000FF;">)</span> |
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">({</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">200</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2000</span><span style="color: #0000FF;">},</span><span style="color: #000000;">plcmz</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 694: | Line 855: | ||
2,000: 151,117,794,877,444,...,415,805,463,680,000 (867 digits) |
2,000: 151,117,794,877,444,...,415,805,463,680,000 (867 digits) |
||
</pre> |
</pre> |
||
=={{header|Picat}}== |
|||
===lcm/2=== |
|||
<code>lcm/2</code> is defined as: |
|||
<syntaxhighlight lang="picat">lcm(X,Y) = X*Y//gcd(X,Y).</syntaxhighlight> |
|||
===Iteration=== |
|||
<syntaxhighlight lang="picat">smallest_multiple_range1(N) = A => |
|||
A = 1, |
|||
foreach(E in 2..N) |
|||
A := lcm(A,E) |
|||
end.</syntaxhighlight> |
|||
===fold/3=== |
|||
<syntaxhighlight lang="picat">smallest_multiple_range2(N) = fold(lcm, 1, 2..N).</syntaxhighlight> |
|||
===reduce/2=== |
|||
<syntaxhighlight lang="picat">smallest_multiple_range3(N) = reduce(lcm, 2..N).</syntaxhighlight> |
|||
===Testing=== |
|||
Of the three implementations the <code>fold/3</code> approach is slightly faster than the other two. |
|||
<syntaxhighlight lang="picat">main => |
|||
foreach(N in [10,20,200,2000]) |
|||
println(N=smallest_multiple_range2(N)) |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10 = 2520 |
|||
20 = 232792560 |
|||
200 = 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
|||
2000 = 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">""" Rosetta code task: Smallest_multiple """ |
||
from math import gcd |
from math import gcd |
||
Line 710: | Line 903: | ||
for i in [10, 20, 200, 2000]: |
for i in [10, 20, 200, 2000]: |
||
print(str(i) + ':', reduce(lcm, range(1, i + 1)))</ |
print(str(i) + ':', reduce(lcm, range(1, i + 1)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>10: 2520 |
|||
20: 232792560 |
|||
200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
|||
2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000</pre> |
|||
=={{header|Quackery}}== |
|||
<code>lcm</code> is defined at [[Least common multiple#Quackery]]. |
|||
<syntaxhighlight lang="Quackery"> [ 1 swap times [ i 1+ lcm ] ] is smalmul ( n --> n ) |
|||
' [ 10 20 200 2000 ] witheach [ dup echo say ": " smalmul echo cr ]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10: 2520 |
<pre>10: 2520 |
||
20: 232792560 |
20: 232792560 |
||
Line 720: | Line 927: | ||
Exercise with some larger values as well. |
Exercise with some larger values as well. |
||
<lang |
<syntaxhighlight lang="raku" line>say "$_: ", [lcm] 2..$_ for <10 20 200 2000></syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 729: | Line 936: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "working..." + nl |
see "working..." + nl |
||
see "Smallest multiple is:" + nl |
see "Smallest multiple is:" + nl |
||
Line 749: | Line 956: | ||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 756: | Line 963: | ||
232792560 |
232792560 |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
{{trans|BASIC}} |
|||
≪ 2 3 * 5 * 7 * 9 * 11 * 13 * 17 * 19 * → t |
|||
≪ t 2 20 '''FOR''' lim |
|||
'''IF''' DUP lim MOD '''THEN''' 1 'lim' STO t + '''END NEXT''' |
|||
≫ ≫ '<span style="color:blue">TASK</span>' STO |
|||
With <code>LCM</code> defined at [[Least common multiple#RPL|Least common multiple]]: |
|||
≪ 1 2 20 '''FOR''' n n <span style="color:blue">LCM</span> '''NEXT''' ≫ '<span style="color:blue">TASK</span>' STO |
|||
{{out}} |
|||
<pre> |
|||
1: 232792560 |
|||
</pre> |
</pre> |
||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby"> |
|||
[10, 20, 200, 2000].each {|n| puts "#{n}: #{(1..n).inject(&:lcm)}" }</syntaxhighlight> |
|||
{{out}} |
|||
<pre>10: 2520 |
|||
20: 232792560 |
|||
200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 |
|||
2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000 |
|||
</pre> |
|||
=={{header|Verilog}}== |
=={{header|Verilog}}== |
||
{{trans|Yabasic}} |
{{trans|Yabasic}} |
||
< |
<syntaxhighlight lang="verilog">module main; |
||
integer temp, smalmul, lim; |
integer temp, smalmul, lim; |
||
Line 780: | Line 1,008: | ||
$finish ; |
$finish ; |
||
end |
end |
||
endmodule</ |
endmodule</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>232792560</pre> |
<pre>232792560</pre> |
||
Line 793: | Line 1,021: | ||
More formally and quite quick by Wren standards at 0.017 seconds: |
More formally and quite quick by Wren standards at 0.017 seconds: |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
import "./big" for BigInt |
import "./big" for BigInt |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Line 809: | Line 1,037: | ||
System.print("The LCMs of the numbers 1 to N inclusive is:") |
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))</ |
for (i in [10, 20, 200, 2000]) Fmt.print("$,5d: $,i", i, lcm.call(i))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 821: | Line 1,049: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">int N, D; |
||
[N:= 2*3*5*7*11*13*17*19; |
[N:= 2*3*5*7*11*13*17*19; |
||
D:= 1; |
D:= 1; |
||
Line 829: | Line 1,057: | ||
until D = 20; |
until D = 20; |
||
IntOut(0, N); |
IntOut(0, N); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 838: | Line 1,066: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|XPL0}} |
{{trans|XPL0}} |
||
< |
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Smallest_multiple |
||
// by Galileo, 05/2022 |
// by Galileo, 05/2022 |
||
Line 848: | Line 1,076: | ||
if mod(N, D) D = 1 : N = N + M |
if mod(N, D) D = 1 : N = N + M |
||
until D = 20 |
until D = 20 |
||
print N</ |
print N</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>232792560 |
<pre>232792560 |
Latest revision as of 10:42, 30 May 2024
- 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
11l
F f(n)
V ans = BigInt(1)
L(i) 1..n
ans *= BigInt(i) I/ gcd(BigInt(i), BigInt(ans))
R ans
L(n) [10, 20, 200, 2000]
print(n‘: ’f(n))
- Output:
10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
ALGOL 68
Uses Algol 68G's LONG LONG INT which has specifiable precision.
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
- 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
Arturo
print first select.first range.step:20 20 ∞ 'x ->
every? 11..19 'z -> zero? x % z
- Output:
232792560
Asymptote
int temp = 2*3*5*7*11*13*17*19;
int smalmul = temp;
int lim = 1;
while (lim <= 20) {
lim = lim + 1;
while (smalmul % lim != 0) {
lim = 1;
smalmul = smalmul + temp;
}
}
write(smalmul);
AutoHotkey
primes := 1
loop 20
if prime_numbers(A_Index).Count() = 1
primes *= A_Index
loop
{
Result := A_Index*primes
loop 20
if Mod(Result, A_Index)
continue, 2
break
}
MsgBox % Result
return
prime_numbers(n) { ; http://www.rosettacode.org/wiki/Prime_decomposition#Optimized_Version
if (n <= 3)
return [n]
ans := [], done := false
while !done
{
if !Mod(n,2){
ans.push(2), n /= 2
continue
}
if !Mod(n,3) {
ans.push(3), n /= 3
continue
}
if (n = 1)
return ans
sr := sqrt(n), done := true
; try to divide the checked number by all numbers till its square root.
i := 6
while (i <= sr+6){
if !Mod(n, i-1) { ; is n divisible by i-1?
ans.push(i-1), n /= i-1, done := false
break
}
if !Mod(n, i+1) { ; is n divisible by i+1?
ans.push(i+1), n /= i+1, done := false
break
}
i += 6
}
}
ans.push(n)
return ans
}
- Output:
232792560
BASIC
BASIC256
temp = 2*3*5*7*11*13*17*19
smalmul = temp
lim = 1
do
lim += 1
if (smalmul mod lim) then lim = 1 : smalmul += temp
until lim = 20
print smalmul
- Output:
232792560
PureBasic
OpenConsole()
temp.i = 2*3*5*7*11*13*17*19
smalmul.i = temp
lim.i = 1
Repeat
lim + 1
If (smalmul % lim)
lim = 1
smalmul = smalmul + temp
EndIf
Until lim = 20
PrintN(Str(smalmul))
Input()
CloseConsole()
- Output:
232792560
True BASIC
LET temp = 2*3*5*7*11*13*17*19
LET smalmul = temp
LET lim = 1
DO
LET lim = lim+1
IF (REMAINDER(ROUND(smalmul),ROUND(lim)) <> 0) THEN
LET lim = 1
LET smalmul = smalmul+temp
END IF
LOOP UNTIL lim = 20
PRINT smalmul
END
- Output:
232792560
Delphi
function IsDivisible120(N: integer): boolean;
{Is N evenly divisible by numbers 1..20}
var I: integer;
begin
Result:=False;
{For speed - larger numbers less likely divisor}
for I:=20 downto 2 do
if (N mod I)<>0 then exit;
Result:=True;
end;
procedure SmallestDivide120(Memo: TMemo);
var I: integer;
begin
{Only look at even numbers for speed}
for I:=1 to High(Integer) do
if IsDivisible120(I*2) then
begin
Memo.Lines.Add(FloatToStrF(I*2,ffNumber,18,0));
break;
end;
end;
- Output:
232,792,560 Elapsed Time: 920.406 ms.
EasyLang
fastfunc isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
n = 20
res = 1
for p = 2 to n
if isprim p = 1
f = p
while f * p <= n
f = f * p
.
res *= f
.
.
print res
- Output:
232792560
F#
This task uses Extensible Prime Generator (F#)
// Least Multiple. Nigel Galloway: October 22nd., 2021
let fG n g=let rec fN i=match i*g with g when n>g->fN g |_->i in fN g
let leastMult n=let fG=fG n in primes32()|>Seq.takeWhile((>=)n)|>Seq.map fG|>Seq.reduce((*))
printfn $"%d{leastMult 20}"
- Output:
232792560
Factor
USING: math.functions math.ranges prettyprint sequences ;
20 [1,b] 1 [ lcm ] reduce .
- Output:
232792560
Fermat
Func Ilog( n, b ) =
i:=0; {integer logarithm of n to base b, positive only}
while b^i<=n do
i:+;
od;
i-1.;
Func Smalmul( n ) =
s:=1;
for a = 1 to n do
if Isprime(a) then s:=s*a^Ilog(n, a) fi;
od;
s.;
!Smalmul(20);
- Output:
232792560
FreeBASIC
Use the code from the Least common multiple example as an include.
#include"lcm.bas"
redim shared as ulongint smalls(0 to 1) 'calculate and store as we go
smalls(0) = 0: smalls(1) = 1
function smalmul(n as longint) as ulongint
if n<0 then return smalmul(-n) 'deal with negative input
dim as uinteger m = ubound(smalls)
if n<=m then return smalls(n) 'have we calculated this already
'if not, make room for the next bunch of terms
redim preserve as ulongint smalls(0 to n)
for i as uinteger = m+1 to n
smalls(i) = lcm(smalls(i-1), i)
next i
return smalls(n)
end function
for i as uinteger = 0 to 20
print i, smalmul(i)
next i
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))
}
}
- Output:
The LCMs of the numbers 1 to N inclusive is: 10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
Haskell
import Text.Printf (printf)
--- SMALLEST INTEGER EVENLY DIVISIBLE BY EACH OF [1..N] --
smallest :: Integer -> Integer
smallest =
foldr lcm 1 . enumFromTo 1
--------------------------- TEST -------------------------
main :: IO ()
main =
(putStrLn . unlines) $
showSmallest <$> [10, 20, 200, 2000]
------------------------- DISPLAY ------------------------
showSmallest :: Integer -> String
showSmallest =
((<>) . (<> " -> ") . printf "%4d")
<*> (printf "%d" . smallest)
- Output:
10 -> 2520 20 -> 232792560 200 -> 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000 -> 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
J
*./ >: i. 20
232792560
jq
Works with jq (*)
Works with gojq, the Go implementation of jq
The following uses `is_prime` as defined at Erdős-primes#jq.
(*) The C implementation of jq has sufficient accuracy for N == 20 but not N == 200, so the output shown below is based on a run of gojq.
# Output: a stream of primes less than $n in increasing order
def primes($n):
2, (range(3; $n; 2) | select(is_prime));
# lcm of 1 to $n inclusive
def lcm:
. as $n
| reduce primes($n) as $p (1;
. * ($p | until(. * $p > $n; . * $p)) ) ;
"N: LCM of the numbers 1 to N inclusive",
( 10, 20, 200, 2000
| "\(.): \(smallest_multiple)" )
- Output:
N: LCM of the numbers 1 to N inclusive 10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
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
Mathematica / Wolfram Language
LCM @@ Range[20]
- Output:
232792560
OCaml
let rec gcd a = function
| 0 -> a
| b -> gcd b (a mod b)
let lcm a b =
a * b / gcd a b
let smallest_multiple n =
Seq.(ints 1 |> take n |> fold_left lcm 1)
let () =
Printf.printf "%u\n" (smallest_multiple 20)
- Output:
232792560
Pascal
Here the simplest way, like Raku, check the highest exponent of every prime in range
Using harded coded primes.
{$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.
- 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.
{$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.
- 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
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Smallest_multiple#Raku
use warnings;
use ntheory qw( lcm );
print "for $_, it's @{[ lcm(1 .. $_) ]}\n" for 10, 20;
- Output:
for 10, it's 2520 for 20, it's 232792560
Phix
Using the builtin, limited to 253 aka N=36 on 32-bit, 264 aka N=46 on 64-bit.
with javascript_semantics ?lcm(tagset(20))
- Output:
232792560
Using gmp
with javascript_semantics include mpfr.e procedure plcmz(integer n) sequence primes = get_primes_le(n) mpz res = mpz_init(1) for i=1 to length(primes) do integer p = primes[i], f = p while f*p <= n do f *= p end while mpz_mul_si(res,res,f) end for printf(1,"%,5d: %s\n", {n, shorten(mpz_get_str(res,10,true))}) end procedure printf(1,"The LCMs of the numbers 1 to N inclusive is:\n") papply({10,20,200,2000},plcmz)
- Output:
The LCMs of the numbers 1 to N inclusive is: 10: 2,520 20: 232,792,560 200: 337,293,588,832,926,...,677,390,066,992,000 (90 digits) 2,000: 151,117,794,877,444,...,415,805,463,680,000 (867 digits)
Picat
lcm/2
lcm/2
is defined as:
lcm(X,Y) = X*Y//gcd(X,Y).
Iteration
smallest_multiple_range1(N) = A =>
A = 1,
foreach(E in 2..N)
A := lcm(A,E)
end.
fold/3
smallest_multiple_range2(N) = fold(lcm, 1, 2..N).
reduce/2
smallest_multiple_range3(N) = reduce(lcm, 2..N).
Testing
Of the three implementations the fold/3
approach is slightly faster than the other two.
main =>
foreach(N in [10,20,200,2000])
println(N=smallest_multiple_range2(N))
end.
- Output:
10 = 2520 20 = 232792560 200 = 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000 = 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
Python
""" Rosetta code task: Smallest_multiple """
from math import gcd
from functools import reduce
def lcm(a, b):
""" least common multiple """
return 0 if 0 == a or 0 == b else (
abs(a * b) // gcd(a, b)
)
for i in [10, 20, 200, 2000]:
print(str(i) + ':', reduce(lcm, range(1, i + 1)))
- Output:
10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
Quackery
lcm
is defined at Least common multiple#Quackery.
[ 1 swap times [ i 1+ lcm ] ] is smalmul ( n --> n )
' [ 10 20 200 2000 ] witheach [ dup echo say ": " smalmul echo cr ]
- Output:
10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
Raku
Exercise with some larger values as well.
say "$_: ", [lcm] 2..$_ for <10 20 200 2000>
- Output:
10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
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
- Output:
working... Smallest multiple is: 232792560 done...
RPL
≪ 2 3 * 5 * 7 * 9 * 11 * 13 * 17 * 19 * → t
≪ t 2 20 FOR lim
IF DUP lim MOD THEN 1 'lim' STO t + END NEXT
≫ ≫ 'TASK' STO
With LCM
defined at Least common multiple:
≪ 1 2 20 FOR n n LCM NEXT ≫ 'TASK' STO
- Output:
1: 232792560
Ruby
[10, 20, 200, 2000].each {|n| puts "#{n}: #{(1..n).inject(&:lcm)}" }
- Output:
10: 2520 20: 232792560 200: 337293588832926264639465766794841407432394382785157234228847021917234018060677390066992000 2000: 151117794877444315307536308337572822173736308853579339903227904473000476322347234655122160866668946941993951014270933512030194957221371956828843521568082173786251242333157830450435623211664308500316844478617809101158220672108895053508829266120497031742749376045929890296052805527212315382805219353316270742572401962035464878235703759464796806075131056520079836955770415021318508272982103736658633390411347759000563271226062182345964184167346918225243856348794013355418404695826256911622054015423611375261945905974225257659010379414787547681984112941581325198396634685659217861208771400322507388161967513719166366839894214040787733471287845629833993885413462225294548785581641804620417256563685280586511301918399010451347815776570842790738545306707750937624267501103840324470083425714138183905657667736579430274197734179172691637931540695631396056193786415805463680000
Verilog
module main;
integer temp, smalmul, lim;
initial begin
temp = 2*3*5*7*11*13*17*19;
smalmul = temp;
lim = 1;
while (lim <= 20) begin
lim = lim + 1;
while (smalmul % lim != 0) begin
lim = 1;
smalmul = smalmul + temp;
end
end
$display(smalmul);
$finish ;
end
endmodule
- Output:
232792560
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:
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))
- 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
XPL0
int N, D;
[N:= 2*3*5*7*11*13*17*19;
D:= 1;
repeat D:= D+1;
if rem(N/D) then
[D:= 1; N:= N + 2*3*5*7*11*13*17*19];
until D = 20;
IntOut(0, N);
]
- Output:
232792560
Yabasic
// Rosetta Code problem: http://rosettacode.org/wiki/Smallest_multiple
// by Galileo, 05/2022
M = 2*3*5*7*11*13*17*19
N = M
D = 1
repeat
D = D + 1
if mod(N, D) D = 1 : N = N + M
until D = 20
print N
- Output:
232792560 ---Program done, press RETURN---
- Draft Programming Tasks
- 11l
- ALGOL 68
- ALGOL 68-primes
- Arturo
- Asymptote
- AutoHotkey
- BASIC
- BASIC256
- PureBasic
- True BASIC
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- Factor
- Fermat
- FreeBASIC
- Go
- Go-rcu
- Haskell
- J
- Jq
- Julia
- Mathematica
- Wolfram Language
- OCaml
- Pascal
- Perl
- Phix
- Picat
- Python
- Quackery
- Raku
- Ring
- RPL
- Ruby
- Verilog
- Wren
- Wren-math
- Wren-big
- Wren-fmt
- XPL0
- Yabasic