世界のナベアツアルゴリズム

３でアホになるナベアツアルゴリズムを考えてみた。ルールは数式縛り。従ってindexOf()とかは反則。
巷にはもっとよい回答があるのだろうけど、とりあえず思いつくところではこんなもんか。

package way.algorithm;

public class Nabeatsu {

	static final int key = 3;//バカになる数字
	static int counter = 0;//計算回数カウンタ

	public static void main(String[] args) {
		int max = 10000;
		for (int i = 0; i < max; i++) {
			if (checkNabeatsu(i)) {
				System.out.println("---" + i + "---");
			} else {
				System.out.println(i);
			}
		}
		System.out.println("計算回数 " + counter + "回");
	}

	public static boolean checkNabeatsu(int p) {
		counter++;
		if (p / 10 == key || p % 10 == key) {
			return true;//ナベアツ確定
		} else if (p / 10 < 10) {
			return false;
		}
		return checkNabeatsu(p / 10);
	}
}

一晩寝て ver.2

package way.algorithm;
public class Nabeatsu {
	static final int key = 3;
	static int counter = 0;
	public static void main(String[] args) {
		int max = 10000;
		for (int i = 0; i < max; i++) {
			for(int k=i;;k/=10){
				counter++;
				if (k % 10 == key ) {
					System.out.println("---" + i + "---");
					break;
				}else if(k < 10){
					System.out.println(i);
					break;
				}
			}
		}
		System.out.println("計算回数 " + counter + "回");
	}
}

どうやら３のつく数字だけじゃなく３の倍数も含めるらしいのと、30〜39,300〜399,3000〜3999のように連続することが分かっている場合は１桁ごとの計算を省略させたい。
という訳でver.3

package way.algorithm;

public class Nabeatsu {
	public static void main(String[] args) {
		final int key = 3;
		int max = 10000;
		int counter = 0;
		int skipLoop = 0;
		for (int i = 1; i <= max; i++) {
			// 数字ごとに下１桁から順にチェックする。何桁目を評価中かをdに格納
			for (int k = i, d = 1;; k /= 10, d *= 10) {
				counter++;
				// ３で割り切れるか、３を含むか、短縮ループ中かをチェック
				if (i % key == 0 || k % 10 == key || skipLoop > 0) {
					// ３を含む位はSKIPモードに移行
					if (skipLoop == 0 && d > 1) {
						skipLoop = d - i % (d * k);
					}
					System.out.println("---" + i + "---");
					if (skipLoop > 0) {
						skipLoop--;
					}
					break;
				} else if (k < 10) {
					// 全ての桁チェックが終わったら対象外確定
					System.out.println(i);
					break;
				}
			}
		}
		System.out.println("計算回数 " + counter + "回");
	}
}

[実行結果]
1
2
☆3☆
4
5
☆6☆
7
8
☆9☆
10
〜 中略 〜
☆9990☆
9991
9992
☆9993☆
9994
9995
☆9996☆
9997
9998
☆9999☆
10000
計算回数 22682回

とりあえずこれ以上は思いつかないのと、所要時間を考えると自信を失うのに十分な時間をかけたと記しておいて終了。