TopCoder SRM 617 Div1 Easy MyLongCake

問題

長いケーキがある。
nの約数のうちn以外の人数の友達が来る可能性がある。
どの人数の友達が来ても、ケーキを連続する区間で同じ長さだけ配れるようにするため、
切れ目を入れておく、切れ目の数の最小値を求めよ。

制約条件

n≦100000

方針

ケーキは連続する区間で配らなければならないので、単に切るべき場所
（2人ならn/2, n, 3人ならn/3, 2n/3, n……)にフラグを立てていくだけでよい。

ソースコード

bool f[110000];

class MyLongCake {
	public:
	int cut(int n) {
		memset(f, 0, sizeof(f));
		
		for(int i = 2; i <= n; i++) if(n % i == 0){
			for(int j = i; j <= n; j += i) f[j] = 1;
		}
		int ans = 0;
		rep(i, n + 1) if(f[i]) ans++;
		return ans;
	}
};