I need to write a program, which prints out all the prime numbers between two numbers. The first input specifies the number of test cases, followed by the limits. Here is an example..
Input:
2
1 10
3 5Output:
2
3
5
73
5
I wrote the following code, but it exceeds the time limit of 6seconds. How can I optimize it to perform faster?
#include<iostream>
#include<cmath>
using namespace std;
bool prime(long);
long primegen(long, long);
int main()
{
int n;
long i,j;
cin>>n;;
while(n--!=0)
{
cin>>i>>j;
if((j-i) <= 100000)
primegen(i,j);
cout<<"\n";
}
return 0;
}
long primegen(long i, long j)
{
long min=i, max= j;
while(min<=max)
{
if(prime(min))
printf("%ld \n", min);
if(min==1 || min % 2 == 0)
min++;
else
min=min+2;
}
return 0;
}
bool prime(long num)
{
double j= (double)num;
if(num == 1)
return false;
if(num == 2)
return true;
if(num % 2 == 0)
return false;
for(int i=3; i<= sqrt(j); i=i+2)
if(num % i == 0)
return false;
return true;
}