Problem 5

久しぶりにデスクトップPCの前に座ったので続きを。

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。 では、1 から 20 までの整数全てで割り切れる数字の中で最小の値はいくらになるか。

Problem 5 - PukiWiki

手っ取り早く、アルゴリズムもクソもない解き方をしてみる。

#include <stdio.h>

#define NUM_MAX 20
/* #define NUM_MAX 10 */

int divideall(int target) {
    int i;
    for (i=2; i<NUM_MAX; i++) {
        if (target % i != 0) {
            return -1;
        }
    }
    return 0;
}

void problem005()
{
    int ans;
    
    /* solve this problem here */
    ans = 1;
    while (divideall(ans) < 0) {
        ans++;
    }                

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

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

実行結果

$ ./problem005
problem005: answer = 232792560

あまりにも愚直すぎるので、もうちょっとマシな方法思いついたら追記する。

追記

せっかく「1から10まで」の場合は2520だと教えてくれているので、利用することにした。
「1から20まで」の場合は、2520の倍数になっているはず。
なので、

#define INCR_STEP 2520

として、ループを以下のように変えちゃいました。

    ans = INCR_STEP;
    while (divideall(ans) < 0) {
        //ans++;
        ans += INCR_STEP;
    }                

無事同じ結果が得られました。
# あ、divideall内のforループの開始値も2じゃなくて11にすればもっと効率的だな…