Hello guys, I am stuck in a medium level problem PRIME1. I used sieve to generate primes upto 32000 (My first sieve implementation, so if it is wrong, please point out.) and used those primes to generate all others, but I am getting TLE. I have looked previous posts and answers in the editorial but was not able to solve it. Please help.

Here is the id of the solution : 4335757

I am also posting it here :

#include<stdio.h>

#define MAX_PRIME 32000

int primes[MAX_PRIME],req_prime[MAX_PRIME];

int total_prime=0;

/*Initialise the array to 1*/

void set_to_one()

{

```
for(int i=0;i<MAX_PRIME;i++)
primes[i]=1;
```

}

/*Finds primes upto 32000 and puts them in another array req_prime*/

void preprocess()

{

```
primes[0]=primes[1]=0;
for(int i=2;i<MAX_PRIME;i++)
{
if(primes[i])
{
req_prime[total_prime++]=i;
for(int j=i+i;j<MAX_PRIME;j+=i)
{
primes[j]=0;
}
}
}
```

}

/*Just to check if all primes are identified or not. They are for debugging only.*/

void print_all_primes()

{

```
for(int i=0;i<MAX_PRIME;i++)
printf("%d\t",primes[i]);
```

}

/*To check if the number is a prime or not*/

void check_prime(int n)

{

```
int count=0;
for(int i=0;i<total_prime;i++)
{
if(n%req_prime[i]==0 && n!=req_prime[i])
count++;
if(req_prime[i]>=n)
break;
}
if(count==0 && n!=1)
printf("%d\n",n);
```

}

/* Checks all numbers in the array */

void solve_problem(int arr[],int size)

{

```
for(int i=0;i<size;i++)
{
check_prime(arr[i]);
}
```

}

int main()

{

```
int test,a,b;
scanf("%d",&test);
set_to_one();
preprocess();
//print_all_primes();
while(test--)
{
scanf("%d%d",&a,&b);
int arr[b-a+1];
for(int i=a;i<=b;i++)
arr[i-a]=i;
solve_problem(arr,b-a+1);
}
return 0;
```

}