Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-06SRM388 (Practice)

SRM 388 SmoothNumbers

|  SRM 388 SmoothNumbers - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 388 SmoothNumbers - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8519

  • 方針を検討
    • 最大kまでの素因数が使えるのか
    • k+1以上の素因数を持つ数をエラトステネスの篩みたいな感じで除外していけばよさそう
      • 念のため、予め素数を列挙しておこう
  • 実装
    • 午前中emacsでAOJやってたのでeclipseでのコーディングに戸惑う
  • サンプル通る。
  • 疑心暗鬼フェーズ
    • 自明なケース (k=1) などでテスト
    • 問題分を読みなおす
      • 最大の素因数がkっていうところが妙に引っかかる
      • 本当にこのやり方で合ってるのか?
    • いや、大丈夫なはず。k+1以上の素因数を持つ数が全部除外されてるのだから
  • 提出

import java.util.Arrays;

public class SmoothNumbers {
	public int countSmoothNumbers(int N, int k) {
		boolean[] isprime = new boolean[200000];
		Arrays.fill(isprime, true);
		isprime[1] = false;
		for (int i = 2 ; i < 200000 ; i++) {
			if (isprime[i]) {
				for (int j = i * 2 ; j < 200000 ; j += i) {
					isprime[j] = false;
				}
			}
		}
		
		boolean[] isksmooth = new boolean[N+1];
		Arrays.fill(isksmooth, true);
		for (int i = k+1 ; i <= N ; i++) {
			if (isprime[i]) {
				for (int j = i ; j <= N ; j += i) {
					isksmooth[j] = false;
				}
			}
		}

		int cnt = 0;
		for (int i = 1 ; i <= N ; i++) {
			if (isksmooth[i]) {
				cnt++;
			}
		}
		return cnt;
	}
}