title: Finding divisor pairs
body: <p>I'm trying to solve this exercise <a href="http://main.edu.pl/en/archive/amppz/2014/dzi" rel="nofollow">http://main.edu.pl/en/archive/amppz/2014/dzi</a> and I have no idea how to improve perfomance of my code. Problems occure when program have to handle over 500,000 unique numbers(up to 2,000,000 as in description). Then it took 1-8s to loop over all this numbers. Tests I have used are from <a href="http://main.edu.pl/en/user.phtml?op=tests&amp;c=52014&amp;task=1263" rel="nofollow">http://main.edu.pl/en/user.phtml?op=tests&amp;c=52014&amp;task=1263</a>, and I testing it by command<br>
  <code>program.exe &lt; data.in > result.out</code>  </p>
  
  <p>Description:
  <code>You are given a sequence of <sub>n</sub> integer a<sub>1</sub>, a<sub>2</sub>, ... a<sub>n</sub>. You should determine the number of such ordered pairs(<sub>i</sub>, <sub>j</sub>), that <sub>i</sub>, <sub>j</sub> equeals(1, ..., <sub>n</sub>), <sub>i</sub> != <sub>j</sub> and a<sub>i</sub> is divisor of a<sub>j</sub>.<br>
  The first line of input contains one integer <sub>n</sub>(1 &lt;= <sub>n</sub> &lt;= 2000000) 
  The second line contains a sequence of <sub>n</sub> integers a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>(1 &lt;= a<sub>i</sub> &lt;= 2000000).<br>
  In the first and only line of output should contain one integer, denoting the number of pairs sought.<br>
  For the input data:
  5
  2 4 5 2 6<br>
  the correct answer is: 6<br>
  Explanation: There are 6 pars: (1, 2) = 4/2, (1, 4) = 2/2, (1, 5) = 6/2, (4, 1) = 2/2, (4, 2) = 4/2, (4, 5) = 6/2.
  </code></p>
  
  <p>For example:<br>
   - with 2M in total numbers and 635k unique numbers, there is 345mln iterations in total<br>
   - with 2M in total numbers and 2mln unqiue numbers, there is 1885mln iterations in total</p>
  
  <pre class="lang-cpp prettyprint-override"><code>#include &lt;iostream&gt;
  #include &lt;math.h&gt;
  #include &lt;algorithm&gt;
  
  #include &lt;time.h&gt;
  
  
  #define COUNT_SAME(count) (count - 1) * count
  
  
  int main(int argc, char **argv) {
      std::ios_base::sync_with_stdio(0);
  
      int n; // Total numbers
      scanf("%d", &amp;n);
  
      clock_t start, finish;
      double  duration;
  
      int minVal = 2000000;
      long long *countVect = new long long[2000001]; // 1-2,000,000; Here I'm counting duplicates
  
      unsigned long long counter = 0;
      unsigned long long operations = 0;
  
      int tmp;
      int duplicates = 0;
  
      for (int i = 0; i &lt; n; i++) {
          scanf("%d", &amp;tmp);
  
          if (countVect[tmp] &gt; 0) { // Not best way, but works
              ++countVect[tmp];
              ++duplicates;
          } else {
              if (minVal &gt; tmp)
                  minVal = tmp;
  
              countVect[tmp] = 1;
          }
      }
  
      start = clock();
  
      int valueJ;
      int sqrtValue, valueIJ;
      int j;
  
      for (int i = 2000000; i &gt; 0; --i) {
          if (countVect[i] &gt; 0) { // Not all fields are setted up
              if (countVect[i] &gt; 1) 
                  counter += COUNT_SAME(countVect[i]); // Sum same values
  
              sqrtValue = sqrt(i);
  
              for (j = minVal; j &lt;= sqrtValue; ++j) {
                  if (i % j == 0) {
                      valueIJ = i / j;
  
                      if (valueIJ != i &amp;&amp; countVect[valueIJ] &gt; 0 &amp;&amp; valueIJ &gt; sqrtValue)
                          counter += countVect[i] * countVect[valueIJ];
  
                      if (i != j &amp;&amp; countVect[j] &gt; 0)
                          counter += countVect[i] * countVect[j];
                  }
  
                  ++operations;
              }
          }
      }
  
      finish = clock();
      duration = (double)(finish - start) / CLOCKS_PER_SEC;
      printf("Loops time: %2.3f", duration);
      std::cout &lt;&lt; "s\n";
      std::cout &lt;&lt; "\n\nCounter: " &lt;&lt; counter &lt;&lt; "\n";
      std::cout &lt;&lt; "Total operations: " &lt;&lt; operations;
  
      std::cout &lt;&lt; "\nDuplicates: " &lt;&lt; duplicates &lt;&lt; "/" &lt;&lt; n;
      return 0;
  }  
  </code></pre>
  
  <p>I know, I shouldn't sort the array at beginning, but I have no idea how to make it in better way.  </p>
  
  <p>Any tips will be great, thanks!</p>
  
  <p>Here is improved algorithm - 2M unique numbers within 0.5s. Thanks to @PJTraill!</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;math.h&gt;
  #include &lt;algorithm&gt;
  
  #include &lt;time.h&gt;
  
  
  #define COUNT_SAME(count) (count - 1) * count
  
  
  int main(int argc, char **argv) {
      std::ios_base::sync_with_stdio(0);
  
      int n; // Total numbers
      scanf("%d", &amp;n);
  
      clock_t start, finish;
      double  duration;
  
      int maxVal = 0;
      long long *countVect = new long long[2000001]; // 1-2,000,000; Here I'm counting duplicates
  
      unsigned long long counter = 0;
      unsigned long long operations = 0;
  
      int tmp;
      int duplicates = 0;
  
      for (int i = 0; i &lt; n; i++) {
          scanf("%d", &amp;tmp);
  
          if (countVect[tmp] &gt; 0) { // Not best way, but works
              ++countVect[tmp];
              ++duplicates;
          } else {
              if (maxVal &lt; tmp)
                  maxVal = tmp;
  
              countVect[tmp] = 1;
          }
      }
  
      start = clock();
  
      int j;
      int jCounter = 1;
  
      for (int i = 0; i &lt;= maxVal; ++i) {
          if (countVect[i] &gt; 0) { // Not all fields are setted up
              if (countVect[i] &gt; 1)
                  counter += COUNT_SAME(countVect[i]); // Sum same values
  
              j = i * ++jCounter;
  
              while (j &lt;= maxVal) {
                  if (countVect[j] &gt; 0)
                      counter += countVect[i] * countVect[j];
  
                  j = i * ++jCounter;
                  ++operations;
              }
  
              jCounter = 1;
          }
      }
  
      finish = clock();
      duration = (double)(finish - start) / CLOCKS_PER_SEC;
      printf("Loops time: %2.3f", duration);
      std::cout &lt;&lt; "s\n";
      std::cout &lt;&lt; "\n\nCounter: " &lt;&lt; counter &lt;&lt; "\n";
      std::cout &lt;&lt; "Total operations: " &lt;&lt; operations;
  
      std::cout &lt;&lt; "\nDuplicates: " &lt;&lt; duplicates &lt;&lt; "/" &lt;&lt; n;
      return 0;
  }
  </code></pre>