fork(4) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define lli long long int
  4. vector<lli> prime(1000001);
  5.  
  6. void sieve()
  7. {
  8. 	for(lli i=0;i<1000001;i++)
  9. 	prime[i]=1;
  10. 	prime[0]=0;
  11. 	prime[1]=0;
  12. 	for(lli i=2;i<1000001;i++)
  13. 	{
  14. 		if(prime[i]==1)
  15. 		{
  16. 			for(lli j=i;i*j<1000001;j++)
  17. 			{
  18. 				prime[i*j]=0;
  19. 			}
  20. 		}
  21. 	}
  22. }
  23. int main()
  24. {
  25. 	sieve();	
  26. 	lli q,l,r;
  27. 	cin>>q;
  28. 	while(q--)
  29. 	{
  30. 		lli count=0;
  31. 		cin>>l>>r;
  32. 		for(lli i=l;i<=r;i++)
  33. 		{
  34. 			lli n=sqrt(l);
  35. 			if(n*n==i)
  36. 			{
  37. 				if(prime[n]==1)
  38. 				count++;
  39. 			}
  40. 		}
  41. 		cout<<count<<"\n";
  42. 	}
  43. 	return 0;
  44. }
  45.  
Time limit exceeded #stdin #stdout 5s 11208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1XJSe9
1
2 6
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!