"Vaishnav and Pizzas" challenge I am trying to solve the below mentioned problem from HackerEarth.

Although the results are fine, the code takes extraordinarily long time to run execute. I am pretty sure the problem is because of the nested loops, and I am working on it.

I would like to know:


How can this code be optimized to run within 1 sec?
What are the general programming principles to optimize your execution time, say while writing embedded applications with time constraints.




#include &lt;iostream&gt;
#include &lt;vector&gt;
using namespace std;



int main(int argc, char * argv[])
{
   int testcase;
   cin &gt;&gt; testcase;
   int Number[10000];
   for(int i = 0; i &lt; testcase ; i++)
   {
      cin &gt;&gt; Number[i];
   }

   float numerator, denominator,result;
   //float myArr[100000];
   vector&lt;float&gt; myArr;

   for(int i = 0; i &lt; testcase ; i++)
   {
      for(int j = 1; j &lt;= Number[i] ; j++)
      {
         for(int k = 1; k &lt;= Number[i] ; k++)
         {
            numerator = j;
            denominator = k;
            //cout &lt;&lt; numerator &lt;&lt; denominator &lt;&lt; endl;
            if(numerator &lt; denominator)
            {
               result = numerator/denominator;
               //cout &lt;&lt; result &lt;&lt; endl;
               bool found = false;
               for(int x=0; x &lt; myArr.size() ; x++)
               {
                  if(result == myArr[x])
                  {
                     found = true;
                     break;
                  }
               }
               if(found == false)
               {
                  myArr.push_back(result);
               }
            }
         }
      }
      cout &lt;&lt; myArr.size() &lt;&lt; endl;
      myArr.clear();
   }

   return 0;
}
Yes, the execution time amounts to O(n^3) because of the nested loops. A brute force approach cannot be healed; you need to change the algorithm.

A given denominator Q produces exactly phi(Q) rational numbers, so the problem boils down to calculating $$ \sum \phi (k) $$

There are many approaches for doing that. For the small numbers (according to constraints, less than 10000) I'd recommend a straightforward use of multiplicative property. A precomputed table of primes may also help.