count predisposition

この問題はエラトステネスの篩を応用したDPによる前計算で解くことができます。
具体的には2～10⁶の配列DPを作り2～10⁶まで以下の動作を繰り返します。
⇒DPiが0の時iの倍数を全て+1する。
クエリが呼ばれた際はDPnを呼び出すことによって問題全体をo(Q+NloglogN)で解くことができました。

またこの問題はspf法(smallest prime facter)を利用して解くことも出来ます。

サンプルコード（python）

dp=[0 for _ in range(10**6+1)]
for i in range(2,10**6+1):
    if dat[i]==0:
        j=i
        while j<=10**6:
            dp[j]+=1
            j+=i
Q=int(input())
for _ in range(Q):
    N=int(input())
    print(dat[N])