Problem 4

左右どちらから読んでも同じ値になる数を回文数という。 2桁の数の積で表される回文数のうち、最大のものは 9009 = 91 × 99 である。
では、3桁の数の積で表される回文数のうち最大のものはいくらになるか。

Problem 4 - PukiWiki

求める数は6桁になるという仮定のもと、各桁の数字を抽出して比較、を繰り返す。

#include <stdio.h>
#include <math.h>

/*
- 999x999から始める。
- 最大のものは6桁になるだろうという前提で処理する(10000 < y < 1000000)
 */
void problem004()
{
    int ans;
    int i, j, target, tmp, digit_num;
    int digit[6];

    /* solve this problem here */
    ans = 0;
    for (i=999; i>=101; i--) {
        for (j=999; j>=101; j--) {
            target = i * j;
            if (target < ans || target < 100000) {
                /* 現状の最大値より小さいまたは5桁になったらループを一つ抜ける */
                break;
            }
            for (digit_num=0; digit_num < 6; digit_num++) {
                tmp = (int)pow(10, digit_num+1);
                digit[digit_num] = target - ((target / tmp) * tmp);
                digit[digit_num] /= (int)pow(10, digit_num);
            }
            if (digit[0] == digit[5]
                && digit[1] == digit[4]
                && digit[2] == digit[3])
            {
                if (target > ans) {
                    printf("(i,j) = (%d, %d), i*j = %d\n", i, j, target);
                    ans = target;
                }
            }
        }
    }

    printf("%s: answer = %d\n", __FUNCTION__, ans);
}

int main(int argc, char* argv[]) 
{
    problem004();
    return 0;
}

実行結果

$ ./problem004
(i,j) = (995, 583), i*j = 580085
(i,j) = (993, 913), i*j = 906609
problem004: answer = 906609

、