# Untitled

unknown
plain_text
a month ago
1.1 kB
5
Indexable
Never
```#include <bits/stdc++.h>
using namespace std ;
#define ll long long
#define For(n) for(int i = 0; i < n; i++)
#define endl '\n'
const  int mx = 2000001;
bool isPrime (int n)
{
if (n == 2) return true;
if (n < 2 || n%2 == 0) return false;
for (ll i = 3; i*i <= n; i+=2)
if(n%i == 0) return false;
return true;
}
vector<ll> primestoN(int n)
{
vector<ll> primes;
primes.push_back(2);
for (ll i = 3;i*i <= n*n; i+=2)
if(isPrime(i))
primes.push_back(i);
return primes;
}
int sum[mx]{};//2 3 5 7 11 13
void solve ()
{
vector<ll>primes = primestoN(mx);
for (int i = 0; i <primes.size(); i++)
for (size_t j = i; primes[j]*primes[i] < mx; j++)
sum[primes[j]*primes[i]] = 1;
for(int i = 1; i <mx ;i++) sum[i] += sum[i-1];
// For(10) cout << sum[i]<< ' ';
int q;cin>>q;
while (q--)
{
int l,r;cin>>l>>r;
cout << sum[r] - sum[l-1] << endl;
}

}

signed main ()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
// cin>>t;
while(t--)
{
solve();
}
return 0;
}```
Leave a Comment