Problem 5　 Smallest multiple

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？

　意味は、「2520は1～10の全ての数字で割り切れる数値の中で最小の値です。では、1～20の全ての数字で割り切れる数値の中で最小の値を求めなさい」。

　FreeMatは剰余計算modも配列で行えます。従って、1～nまでの配列mを用意して、mod(k,m)が全て0となれば、kは1～nの全ての数で割り切れることになります。whileループでmod(k,m)の合計が0になるまでkを増加させると、求める数が得られます。

　以上の考え方をFreeMatのプログラムにしたのが、ex329.mです。

function p5=ex329(n)
    k=n;m=1:n;
    while(sum(mod(k,m))~=0)
        k=k+1;
    end
    p5=k;

ex329.m

＞＞「ex329.m」ダウンロード

　下記のようにコマンドウィンドウに入力すると、2520と正しい結果が得られることが分かります。

--> ex329(10)
ans = 2520

　次は、本番の1～20での計算になりますが、例での計算でもけっこうな時間がかかっています。そこで、処理を高速化させる必要があります。ただ、ex329.mは5行しかないので、高速化させるにも限度があります。

　そこで、考え方を変えてみます。1～nの全ての数で割り切れる最小の数ということは、1～nの最小公倍数になります。そこで、1～nの最小公倍数を求めることにします。1～nの最小公倍数は、1と2の最小公倍数を求め、次に求めた最小公倍数と3との最小公倍数を求めてと、前に求めた最小公倍数と次の数値との最小公倍数を次の数値がnになるまで求めれば得られます。以上をFreeMatのプログラムにしたのがex330.mです。最小公倍数を求める関数をlcm(a,b)として、kを2からnまで増加させながら、lcmを呼び出して計算していきます。

function p5=ex330(n)
    p5=1;
    for k=2:n
        p5=lcm(p5,k);
    end
 
function lc=lcm(a,b)
    m=a;n=b;
    while(m~=n)
        if(m>n)
            m=m-n;
        else
            n=n-m;
        end
    end
    lc=a*b/m;

ex330.m

＞＞「ex330.m」ダウンロード

　本番の1～20の全ての数で割り切れる最小の数値を求めると、以下のようになります。