Prateek loves candy

#1

Following is my code.
It is showing timelimit.
please correct me.

Link - https://ide.codingblocks.com/s/50757

#include
using namespace std;
int main(){
long long int tt;
cin>>tt;
for(int m=0;m<tt;m++)
{
int n;
cin>>n;
int c = 0;
long long int number = 1;
while(c<=n)
{

             int flag = 0;
             for(int i=2;i<=number/2;i++)
             {
              if(number%i == 0)
                {
                 flag = 1;
                 break;
                }
             }
            if(flag == 0)
             {
               c++;
             }
             number++;
         }
         cout<<number-1<<endl;
}


 return 0;

}

#2

Hi Amartya, your code is showing TLE because of the nested loops. This would certainly increase the time complexity. You can try to reduce the time complexity by using more efficient solutions. Try to use the sieve of eratosthenes to find the prime numbers.

#3

maam, i have solved using sieve of eratosthenes, but still it is giving TLE.

#4

Below is the code i have written- #include <bits/stdc++.h> using namespace std; void SieveOfEratosthenes(int n) { bool prime[n+1]; memset(prime, true, sizeof(prime)); for (int p=2; pp<=n; p++) { if (prime[p] == true) { for (int i=pp; i<=n; i += p) prime[i] = false; } } int p,c = 0; for (p=2; p<=n; p++) { if (prime[p]) //cout << p << " "; { c++; if(c == (n/3)) { cout<<p<<endl; break; } } } } int main(){ int tt; cin>>tt; for(int m=0;m<tt;m++) { int n; cin>>n; SieveOfEratosthenes(n*3); } return 0; }

#5

Hey, can you share the online ide link of your code.