「世界のナベアツ」問題

お笑いには非常にうとくて、「世界のナベアツ」という言葉は最近よく目にするなあとは思っていたが、この間はじめてテレビで見たばかりだ。しかし、それは本人ではなかったらしい。

3の倍数、5の倍数、または3のつく数かを判定する。これをプログラムで書くのがはやっているらしい。
http://q.hatena.ne.jp/1207585413

とりあえず、サクッと書いてみた。

#include 
using namespace std;
bool nabeatsu(int n);
int main() {

    for(int n = 1; n <= 30; n++) {

        if(nabeatsu(n))

            cout << n << " ○\n";

        else

            cout << n << " ×\n";

    }

}
bool nabeatsu(int n) {

    if(n % 3 == 0)

        return true;

    

    if(n % 5 == 0)

        return true;

    

    while(n >= 10) {

        int     mod = n % 10;

        if(mod == 3)

            return true;

        n /= 10;

    }

    

    return n == 3;

}

うーん、あまりいいコードを思いつかない。

それよりも、素数判定のときと同じように、1000ずつ区切ってみて、その中で判定にひっかかる個数を数えてみよう。すなわち、1〜1000、1001〜2000、…の間の判定にかかる個数を数える。

#include 
using namespace std;
bool nabeatsu(int n);
int main() {

    for(int n = 1; n < 100000000; n += 1000) {

        int     counter = 0;

        for(int m = n; m < n + 1000; m++)

            counter += (int)nabeatsu(m);

        cout << n << " : " << counter << endl;

    }

}

これで11.2s。