"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 
#include 
using namespace std;

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

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

   for(int i = 0; i < testcase ; i++)
   {
      for(int j = 1; j <= Number[i] ; j++)
      {
         for(int k = 1; k <= Number[i] ; k++)
         {
            numerator = j;
            denominator = k;
            //cout << numerator << denominator << endl;
            if(numerator < denominator)
            {
               result = numerator/denominator;
               //cout << result << endl;
               bool found = false;
               for(int x=0; x < myArr.size() ; x++)
               {
                  if(result == myArr[x])
                  {
                     found = true;
                     break;
                  }
               }
               if(found == false)
               {
                  myArr.push_back(result);
               }
            }
         }
      }
      cout << myArr.size() << 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.

StackExchange Code Review Q#63602, answer score: 5