yukicoder:No.811 約数の個数の最大化
問題
解法
N の素因数をあらかじめ求めておき,1 ~ N - 1 の全ての数について素因数を求め,N の素因数と共通しているものが K 以上あるものは約数の個数を計算し,その約数の個数を最大化するように更新していく.最大の約数の個数を持つ数のうち一番小さいものを出力すればよい.O(N√N).
解答
N の素因数をあらかじめ求めておき,1 ~ N - 1 の全ての数について素因数を求め,N の素因数と共通しているものが K 以上あるものは約数の個数を計算し,その約数の個数を最大化するように更新していく.最大の約数の個数を持つ数のうち一番小さいものを出力すればよい.O(N√N).