コンピュータ「オイラと数学しよう」 ――オイラープロジェクトの問題にチャレンジ（その1）：無償ソフトで技術計算しよう【プログラミング応用編】（2）（2/2 ページ）

「プログラミング応用編」では、プログラミングコンテストの問題などをFreeMatでプログラム作成していく。今回は「オイラープロジェクト」の問題を解こう。

[伊藤孝宏，MONOist]

問題3

3．Problem 3　 Largest prime factor

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143？

　意味は、「13195の素因数は、5,7,13,29です。600851475143の素因数のうち、最大のものを求めなさい」。

　素因数分解は、「nがある数mで割り切れたら、nをn/mで置き換える」ということを、mを1ずつ増加させながら、nが1になるまで繰り返します。割り切れたときのmは素因数となります。素因数のうち、最大のものは最後に割り切れたmになります。

　以上をFreeMatのプログラムにすると、ex326.mになります。

function p3=ex326(n)
    m=2;
    while(n~=1)
        if(mod(n,m)==0)
            n=n/m;
        else
            m=m+1;
        end
    end
    p3=m;

ex326.m

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

　例で試してみると、下記のように29となり、正しいことが分かります。

--> ex326(13195)
ans = 29

　次に、本番の値を入れて、コマンドウィンドウに入力すると、以下の結果が得られます。

--> ex326(600851475143)
ans = 6857

問題4

4．Problem 4　 Largest palindrome product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91×99.

Find the largest palindrome made from the product of two 3-digit numbers.

　意味は、「左右どちらから読んでも同じ値になる数を回文数といいます。2桁（けた）の数の積からなる回文数で最大のものは、9009です。3桁の数の積からなる回文数で最大のものを求めなさい」。

　n桁の数は10^(n-1)から10^n-1になります。最大の回分数を求めるため、大きい方から順に積を作り、回文数になっているかチェックします。回分数のチェックは、積pをnum2strコマンドで文字列Nに変えます。

　次に、fliplrコマンドで左右反転させたものと同じかどうかをstrcmpコマンドで調べます。同じであり、かつ、積pが以前格納した値よりも大きい場合、p4に格納します。

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

function p4=ex327(n)
    n1=10^(n-1);n2=10^n-1;
    p4=0;
    for k1=n2:-1:n1
        for k2=n2:-1:n1
            p=k1*k2;
            N=num2str(p);
            if(strcmp(N,fliplr(N)))
                if(p>p4)
                    p4=p;
                end
                break;
            end
        end
    end

ex327.m

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

　2桁の数で確認してみると、下記のように正しいことが分かります。

--> ex327(2)
ans = 9009

　2桁の数で確認してみると、結構な時間がかかります。このまま3桁の数では時間がかかり過ぎる可能性があります。そこで処理を高速化する方法を考えます。

　積は、A×B＝B×Aの関係があるので、ループの内側のk2は、k1まで計算すればよいことが分かります。

　次に、回文数はA×1000+B×100+ B×10+ A=1001×A+110×B=11×(91×A+10×B)と、11の倍数になります。従って、回文チェックを行う前に、11の倍数であるかを調べて、11の倍数の場合のみ回文チェックを行うようにすれば、処理速度が向上すると考えられます。以上の考え方を入れて、ex327.mを改良したのが、ex328.mになります。これで、本番の3桁の数で計算してみます。

function p4=ex328(n)
    n1=10^(n-1);n2=10^n-1;
    p4=0;
    for k1=n2:-1:n1
        for k2=n2:-1:k1
            p=k1*k2;
            if(mod(p,11)==0)
                N=num2str(p);
                if(strcmp(N,fliplr(N)))
                    if(p>p4)
                        p4=p;
                    end
                 end
            end
        end
    end

ex328.m

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

本当はダメかもしれませんが、仕方ないので……

　ただ、残念ながら、FreeMat自体の処理速度が遅いのか、答えを得るまでには至りませんでした。そこで、おきて破りのようで申し訳ないのですが、MATLABでex328.mを動作させてみると、下記の答えが得られます。読者の皆さんも処理速度を向上させる方法を考えてみてください。

>> ex328(3)
ans = 906609

---

　次回もオイラープロジェクトの問題をFreeMatで解いてみます。

参考文献

• 「MATLABハンドブック」小林一行著、秀和システム刊
• 「はじめてのFreeMat」赤間世紀著、工学社刊

無償ソフトで技術計算しよう

無償ソフトで技術計算しよう

無償の工学計算ソフトでも、かなり高度な計算ができる！

筆者紹介

伊藤孝宏（いとう・たかひろ）

1960年生。小型モーターメーカーのエンジニア。博士（工学）。専門は流体工学、音・振動工学。現在は、LabVIEWを使って、音不良の計測・診断ソフト、特性自動検査装置などの開発を行っている。