Hi,
I implemented the segmented sieve algorithm for this question as follows :
#include <iostream>
#include <string>
#include <set>
#include<math.h>
#include<vector>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define MAX 32000 // sqrt of the upper range
using namespace std;
unsigned base[MAX]; // 0 indicates prime
vector<unsigned> pv; // vector of primes
void sieve(){
for(unsigned i = 2 ; i * i < MAX ; i++ )
if(!base[i])
for(unsigned j = i * i ; j < MAX ; j += i )
base[j] = 1;
for(unsigned i = 2 ; i < MAX ; i++ )
if(!base[i]) pv.push_back(i);
}
unsigned fd_p(unsigned p ,unsigned a ,unsigned b){
while(1){
if(a % p == 0 && a !=p) break;
a++;
}
return a;
}
void seg_sieve(unsigned a , unsigned b){
if(b < 2 ){
cout << "" ;
return;
}
if(a < 2){
a = 2;
}
unsigned i,j;
unsigned seg_size = b - a + 1;
unsigned *is_prime = new unsigned [seg_size];
memset(is_prime,0,seg_size*sizeof(unsigned));
vector<unsigned> :: iterator p ;
for(p = pv.begin(); p!=pv.end(); p++){
unsigned x = fd_p(*p,a,b);
for(i = x; i <= b; i += *p )
is_prime[i - a] = 1;
}
for(i=0; i < b - a + 1; i++)
if(!is_prime[i])
cout<< i + a <<endl;
delete []is_prime ;
}
int main()
{
sieve();
unsigned a,b,T;
cin >> T;
while(T--){
cin >> a >> b;
seg_sieve(a,b);
cout<<"\n";
}
// cout<<endl;
// system("PAUSE");
return 0;
}
I am getting TLE nevertheless .. I don't understand what other optimization would be required . Plz help 