Prime Generator(Prime 1)

[kivtas_7]

The code is showing TLE. Can anyone help optimizing it…

#include
#include <math.h>
using namespace std;

int is_prime(int m)
{
int i,c=0;
for(i=2;i<=sqrt(m);i++)
{
if(m%i==0)
c++;
}

if(c==0)
return 1;
else
return 0;

}
int main() {
int n,m,i,j,k,num;
cin>>num;
for(i=1;i<=num;i++)
{
cin>>m>>n;

int a[n];
for(j=0;j<=n;j++)
a[j]=1;
for(j=2;j<sqrt(n);j++)
{
	if(is_prime(j)==1)
	{
		//l=2;
		for(k=j*j;k<=n;k=k+j)
		{
			a[k]=0;
		}
	}
}
for(j=m;j<=n;j++)
       {
       	if(a[j]==1)
       	cout<<j<<endl;
       
       	
       }
cout<<endl;

}

return 0;

}

[simes]

Ask yourself:

1. How many divisions do you need to do to determine that 1000000000 isn’t prime? How many does your code do?
2. When you set a[k] to 0, this means you know that k isn’t prime - could you use this to reduce the processing you do?
3. Could you store anything between test cases to save recalculating the same data each time?