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

» 2014年11月11日 10時15分 公開
[伊藤孝宏,MONOist]
前のページへ 1|2       

問題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」赤間世紀著、工学社刊

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

FreeMat

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


筆者紹介

伊藤孝宏(いとう・たかひろ)

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



前のページへ 1|2       

Copyright © ITmedia, Inc. All Rights Reserved.