// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx,avx2,fma") #include #define rep(i, a, b) for(int i = (a); i <= (b); i ++) using std::cin, std::cout, std::cerr; using ll = long long; ll Sqrt(ll x) { ll s = std::sqrt(x); while((s + 1) * (s + 1) <= x) s ++; while(s * s > x) s --; return s; } int main() { std::ios::sync_with_stdio(false); ll l, r; cin >> l >> r; ll n = 1e6; std::vector a(r - l + 1); std::vector squarefree(r - l + 1, true); std::iota(a.begin(), a.end(), l); for(ll i = 2; i <= n; i ++) { for(ll j = (l + i * i - 1) / (i * i) * (i * i); j <= r; j += i * i) squarefree[j - l] = false; for(ll j = (l + i - 1) / i * i; j <= r; j += i) while(a[j - l] % i == 0) a[j - l] /= i; } for(ll i = l; i <= r; i ++) if(a[i - l] > 1) { ll s = Sqrt(a[i - l]); if(s * s == a[i - l]) squarefree[i - l] = false; } cout << std::ranges::count(squarefree, true) << '\n'; }