Prateek loves candy-Problem

What should be done to avoid TLE error?
#include
using namespace std;
short int isPrime(int n)
{ for (int i = 2; i <= n-1; i++)
if (n%i == 0)
return 0;

return 1;

}
int candy(int v)
{ int u; int i=0;
for( u=2;i!=v; u++ )
{
isPrime(u) ? i++ : 1 ;
} return u-1;
}
int main() { int T; cin>>T; int y[T]={0};
for(int i=0;i<T;i++)
{
cin>>y[i];

}    if((0<T)&&(T<=10000))

{
for(int i=0;i<T;i++)
{ cout<<candy(y[i])<<endl;
}} return 0;}

you are finding every no is prime or not in O(n) and then you are doing this for every test case.
So, its better to precompute all prime numbers using Sieve.

1 Like