NGIRL Sieve of erastothenes

1

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

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

#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;
	vector<int> gift;
	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.

2

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). :slightly_smiling_face:

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)
#define rmLead(str) str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
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();
}
2 Likes