Ideone.com

fork download

copy

#include <bits/stdc++.h>
#define ll long long int
#define inf 1e18
#define iosbase ios_base::sync_with_stdio(false);
#define mp make_pair
#define pb push_back
#define up upper_bound
#define lb lower_bound
#define MOD 1000000007
#define sc(n) scanf("%lld" , &n);
#define Max 500005
using namespace std;
 
ll mark[Max];
typedef vector<ll> VI;
VI prime;
VI primesq;
 
int main()
{
	iosbase
 
	for(int i=2 ; i<Max ; i++)
	{
        if(mark[i]==0)
        {
            for(int j= i+i ; j<=Max ; j+=i)
			{
				mark[j]++;
			}
			prime.pb(i);
        }
	}
 
	for(int i=0 ; i<prime.size() ; i++)
	{
        ll square = prime[i]*prime[i];
        if(square<0)
        {break;}
        primesq.pb(square);
 
	}
 
	ll test_cases;
	cin>>test_cases;
 
	while(test_cases--)
	{
        ll Start ,  End;
        cin>>Start>>End;
 
        VI::iterator low , high;
 
        low = std::lb(primesq.begin() , primesq.end() , Start);
        high = std::lb(primesq.begin() , primesq.end() , End);
 
        ll lowval = low-primesq.begin();
        ll highval = high-primesq.begin();
 
        ll tag=0; //for base conditions
 
        if(highval !=0  && primesq[highval] > End)
        {
            highval--;
        }
        else if(highval == 0 && primesq[highval] > End )
        {
            tag=1;
        }
 
 
 
        if(lowval>highval | tag)
        {
            cout<<0<<endl;
        }
        else
        {
            cout<<highval-lowval+1<<endl;
        }
 
	}
 
 
 
 
 
 
 
 
	return 0;
}

Runtime error #stdin #stdout 0.08s 8520KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/pBpGqK

language:

C++14 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language