白駿1016

これは、特定の範囲の数が平方で除算されているかどうかを決定する問題です.
この問題の特徴は左の範囲が一組であることだ.
しかしrightは1兆+1百万なので、100万の間の数字の中でどれを選べばいいのか.
もちろん、サイズの配列のセットを作成することは不可能です.
平方で区切られたものをエラトネスのふるいでろ過し、値の範囲100万を配列の先頭インデックスに指定すればよい.
このため,左値以上の最大二乗数を見つけ,その後,エラトニスのふるいで二乗数の倍数を濾過し,元の二乗数を1に高め,エラトニスのふるいで濾過することができる.
平方数が正しい値を超えた瞬間に論理を終了すればよい.

a,b = map(int,input().split())
arr = [0] * (b-a+1)
i = 2
ans = b-a+1
while i*i <= b:
    k = i*i
    remain = 0 if a % k == 0 else 1
    j = a // k + remain
    while k*j <= b:
        if not arr[k*j-a]:
            arr[k*j-a] = 1
            ans -= 1
        j += 1
    i += 1
print(ans)