ある整数を n とし, n の約数の集合を S(n) としよう.
S(n) の部分集合 A が一つの要素のみを含むか, あるいは A のいかなる要素もその他全ての要素によって割り切ることができないとき, それを S(n) の反鎖 (antichain) と呼ぼう.
例えば : S(30) = {1, 2, 3, 5, 6, 10, 15, 30}
{2, 5, 6} は S(30) の反鎖ではない.
{2, 3, 5} は S(30) の反鎖である.
S(n) の反鎖のうち最大の長さとなるもののその長さを N(n) で表すとしよう.
1 ≤ n ≤ 108 のときの ΣN(n) を求めよ.