fork download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. vector<int> primes,squares;
  7.  
  8. void generate(int max){
  9.     for(int i=3; i<=max; i+=2){
  10.         int j=0;
  11.         for(; j<primes.size(); j++){
  12.             if(i%primes[j]==0) break;
  13.         }
  14.         if(j==primes.size()) {
  15.             primes.push_back(i);
  16.             squares.push_back(i*i);
  17.         }
  18.     }
  19. }
  20.  
  21. void testcase(int m, int n){
  22.     if(m<=2 && n>=2) cout << "2\n";
  23.     for(int i=max(3,(m/2)*2+1); i<=n; i+=2){
  24.     	int sqr=(int)sqrt(i);
  25.         for(int j=0; ; j++){
  26.             if(primes[j]>sqr) {
  27.                 //cout << i << '\n';
  28.                 break;
  29.             }
  30.             //if(primes[j]==0) cout << j<<primes.size()<< endl;
  31.             if(i%primes[j]==0) break;
  32.         }
  33.     }
  34. }
  35.  
  36. int main() {
  37. 	// your code goes here
  38. 	generate((int)sqrt(1000000000)+1);
  39. 	//cout << primes.size() << squares.size();
  40. 	int t;
  41. 	cin >> t;
  42. 	for(int i=1; i<=t; i++){
  43. 		int m,n;
  44. 		cin >> m >> n;
  45. 		testcase(m,n);
  46. 		cout<<endl;
  47. 	}
  48. 	return 0;
  49. }
Success #stdin #stdout 0.43s 15240KB
comments (?)
stdin
copy 
1 1 1000000000
stdout
copy 
2
https://ideone.com/D8KPtU
problem PRIME1, based on SPOJ submission 19220272 (CPP14), 2017-04-15 07:27:14
language:
C++14 (gcc 8.3)
created:
7 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!