For the below code , if the inputs are large such as x=11111111 y=11111222 it shows time limit exceeded ? How to overcome this?

Question

#include <iostream>
using namespace std;
bool prime(long long int x)
{
long long int temp=1 ,i;
for(i=2;i<=x/2;i++)
if(x%i==0)
temp=0;
return temp;

}
int main(){
long long int x,y;
int k=0,s;
cin>>s;
while(k<s){
cin>>x>>y;
if(x==1)
x=x+1;
for(long long int i=x;i<=y;i++){
if(prime(i))
cout<<i<<endl;
}
k++;
cout<<endl;
}
}

please help

Answer 1

thanks Dipak Chauhan

Answer 2

Your inner for loop is running for as many time as difference between the value of x and y and in its each iteration it calls a function in which once again the for loop is iterating for half of the value of X which is quite large number of times for such a huge value of X. Try to optimize your code or give a smaller value of input.
Above all there's also a while loop that counts as it loops for the value of S you entered. This would also make the difference.

Answer 3

man you are victim of nested loops.
i tried your program first which runs very slow on my machine.
So i decided to reduce your loops also function calls and variable lists.
And believe me my code run very fast.
Yours is generating 2 o/p for 10 digit no in 1 sec and mine generates about 20-30. or more i cant count it's moving so fast.
Anyway her's my solution

/*----------------------------------------------
Code for generating prime numbers between 2 no.
and repeating it for different input*/

#include<iostream>
#include<cmath>
using namespace std;
int main(){
long long int small,high;
int k;
cin >> k;
while(k > 0){
cin >> small >> high;
while(small <= high){
int flag =0;
for(long long int i = 2; i < sqrt(small); i++){
if(small%i == 0){
flag = 1;
break;
}
}
if(flag == 0) cout << small << endl;
small++;
}
k--;}
return 0;
}

/*This is my first time something this big
Hit thanks if you like **/