# NGIRL Sieve of erastothenes

https://www.spoj.com/problems/NGIRL/

#include <bits/stdc++.h>
using namespace std;
const int N = 10e5 + 7;
int main() {

#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);
#endif

``````vector<int>  a(N, 0);
a[0] = a[1] = 1;
for (int i = 2; i * i <= N; i++)
{
if (a[i] == 0)
{
for (int  j = i * i; j <= N; j += i)
{
a[j] = 1;
}
}
}
int t; cin >> t;
while (t--)
{
long long n, k;
int r = 0, choice = 0;
cin >> n >> k;
for (long long  i = 2; i * i <= n; i++)
{
if (a[i] == 0)
{
r++;
if ((i * i) > k)  choice++;
}
}
cout << r << " " << choice << "\n";
}
return 0;
``````

}

Can anyone explain how to optimize the code?or any other approaches.

The first thing to observe is that number with 3 divisors are squares of some prime no (Eg. 4,9,49,121,…). We can find prime numbers <=1e5 (because numbers are <=10^10 so prime no’s <=10^5 is sufficient )using sieve and append their squares to a vector. Now we can calculate the required numbers using binary search (or upper_bound using cpp stl).

Here’s my solution:

``````#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define f first
#define s second
#define vi vector<ll>
#define vs vector<string>
#define input(v,n) for(ll VAL=0;VAL<n;VAL++){ll VALUE;cin>>VALUE;v.pb(VALUE);}
#define mi map<ll,ll>
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define mi map<ll,ll>
#define print(v) for(ll printing=0;printing<v.size();printing++){cout<<v[printing]<<' ';}
#define TestCase ll testcase;cin>>testcase;while(testcase--)
#define bin(n) bitset<32>(n).to_string();
#define maxv(v) *max_element(v.begin(),v.end())
#define minv(v) *min_element(v.begin(),v.end())
#define decimal(s) stoll(s,nullptr,2)
using namespace std;
vi prime;
void create(){
bool isPrime[100001];
for(ll i=0;i<=100000;i++)
isPrime[i]=true;
for(ll i=2;i<=100000;i++){
if(isPrime[i]==true){
prime.pb(i*i);
for(ll j=i*i;j<=100000;j+=i)
isPrime[j]=false;
}
}
//cout<<"Here";
//print(prime);

}
void solve(){
ll n,k;cin>>n>>k;
//print(prime);
ll v1=upper_bound(prime.begin(),prime.end(),n)-prime.begin();
ll v2=upper_bound(prime.begin(),prime.end(),k)-prime.begin();

cout<<v1<<" "<<max(v1-v2,(ll)0)<<"\n";

}

int main(){
create();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

TestCase
solve();
}
``````
1 Like