SRM 388 250pt: SmoothNumbers

問題概要

xの最大の素因数がkを越えないとき、xをk-smooth numberと呼ぶ。N(<10^5), k(<100)が与えられるので、[1,N]にあるk-smooth numberの数を求める問題。

考えたこと

• 基本的には書くだけに見える。全探索で普通に素因数分解してO(N^(3/2))。
• だが1はどうなんだ？1に素因数なんてないんですけど…。サンプル見ても不明。
• k=1のとき1はsmoothでないとして出したのは通らなかった。
• 訂正して通ったけど後味悪い…。問題文が短かったことくらいしかいい所がない。

practiceで通ったコード

計算量O(N^(3/2))。

struct SmoothNumbers {

	int countSmoothNumbers(int N, int k) {

		int ret = 0;

		//全部試す
		for(int i=1; i<=N; i++){
			if(is_smooth(i, k)){
				ret++;
			}
		}

		return ret;
	}

	bool is_smooth(int x, int k){
		int ma = 0;
		for(int i=2; i*i <= x; i++){
			if(x % i == 0){
				ma = i;
				while(x%i == 0) x /= i;
			}
		}
		if( x != 1) ma = x;
		return ma <= k;
	}

};