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