Finding divisor pairs

Question

I'm trying to solve this exercise http://main.edu.pl/en/archive/amppz/2014/dzi 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 http://main.edu.pl/en/user.phtml?op=tests&c=52014&task=1263, and I testing it by command
program.exe < data.in > result.out

Description: You are given a sequence of n integer a1, a2, ... an. You should determine the number of such ordered pairs(i, j), that i, j equeals(1, ..., n), i != j and ai is divisor of aj.
The first line of input contains one integer n(1 <= n <= 2000000) The second line contains a sequence of n integers a1, a2, ..., an(1 <= ai <= 2000000).
In the first and only line of output should contain one integer, denoting the number of pairs sought.
For the input data: 5 2 4 5 2 6
the correct answer is: 6
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.

For example:
- with 2M in total numbers and 635k unique numbers, there is 345mln iterations in total
- with 2M in total numbers and 2mln unqiue numbers, there is 1885mln iterations in total

#include <iostream>
#include <math.h>
#include <algorithm>

#include <time.h>


#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", &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 < n; i++) {
        scanf("%d", &tmp);

        if (countVect[tmp] > 0) { // Not best way, but works
            ++countVect[tmp];
            ++duplicates;
        } else {
            if (minVal > tmp)
                minVal = tmp;

            countVect[tmp] = 1;
        }
    }

    start = clock();

    int valueJ;
    int sqrtValue, valueIJ;
    int j;

    for (int i = 2000000; i > 0; --i) {
        if (countVect[i] > 0) { // Not all fields are setted up
            if (countVect[i] > 1) 
                counter += COUNT_SAME(countVect[i]); // Sum same values

            sqrtValue = sqrt(i);

            for (j = minVal; j <= sqrtValue; ++j) {
                if (i % j == 0) {
                    valueIJ = i / j;

                    if (valueIJ != i && countVect[valueIJ] > 0 && valueIJ > sqrtValue)
                        counter += countVect[i] * countVect[valueIJ];

                    if (i != j && countVect[j] > 0)
                        counter += countVect[i] * countVect[j];
                }

                ++operations;
            }
        }
    }

    finish = clock();
    duration = (double)(finish - start) / CLOCKS_PER_SEC;
    printf("Loops time: %2.3f", duration);
    std::cout << "s\n";
    std::cout << "\n\nCounter: " << counter << "\n";
    std::cout << "Total operations: " << operations;

    std::cout << "\nDuplicates: " << duplicates << "/" << n;
    return 0;
}  

I know, I shouldn't sort the array at beginning, but I have no idea how to make it in better way.

Any tips will be great, thanks!

Here is improved algorithm - 2M unique numbers within 0.5s. Thanks to @PJTraill!

#include <iostream>
#include <math.h>
#include <algorithm>

#include <time.h>


#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", &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 < n; i++) {
        scanf("%d", &tmp);

        if (countVect[tmp] > 0) { // Not best way, but works
            ++countVect[tmp];
            ++duplicates;
        } else {
            if (maxVal < tmp)
                maxVal = tmp;

            countVect[tmp] = 1;
        }
    }

    start = clock();

    int j;
    int jCounter = 1;

    for (int i = 0; i <= maxVal; ++i) {
        if (countVect[i] > 0) { // Not all fields are setted up
            if (countVect[i] > 1)
                counter += COUNT_SAME(countVect[i]); // Sum same values

            j = i * ++jCounter;

            while (j <= maxVal) {
                if (countVect[j] > 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 << "s\n";
    std::cout << "\n\nCounter: " << counter << "\n";
    std::cout << "Total operations: " << operations;

    std::cout << "\nDuplicates: " << duplicates << "/" << n;
    return 0;
}

Answer 1

I expect the following to work a lot faster than the OP’s algorithm (optimisations oblique):

• (The type of values and frequencies should be 32-bit unsigned, counts 64-bit – promote before calculating a count, if your language would not.)
• Read the number of values, N.
• Read each value v, adding one to its frequency freq[v] (no need to store it).
  • (freq[MAX] (or MAX+1) can be statically allocated for probably optimal initialisation to all 0)
• Calculate the number of pairs involving 1 from freq[1] and the number of values.
• For every i in 2..MAX (with freq[i] > 0):
  • Calculate the number of pairs (i,i) from freq[i].
  • For every multiple m of i in 2m..MAX:
    • (Use m as the loop counter and increment it, rather than multiplying)
    • Calculate the number of pairs (i,m) from freq[i] and freq[m].
  • (if freq[i] = 1, one can omit the (i,i) calculation and perform a variant of the loop optimised for freq[i] = 1)
• (One can perform the previous (outer) loop from 2..MAX/2, and then from MAX/2+1..MAX omitting the processing of multiples)

The number of pairs (i,i) = _freq[i]C₂ = ( freq[i] * (freq[i] - 1) ) / 2 .
The number of pairs (i,j) = freq[i] * freq[j] for i ≠ j.

This avoids sorting, sqrt and division.

Other optimisations

One can store the distinct values, and scan that array instead (the order does not matter); the gain or loss due to this depends on the density of the values in 1..MAX.

If the maximum frequency is < 2¹⁶, which sounds very probable, all products will fit in 32 bits. One could take advantage of this by writing functions with the numeric type as a template, tracking the maximum frequency and then choosing the appropriate instance of the template for the rest. This costs N*(compare+branch) and may gain by performing D² multiplications with 32 bits instead of 64, where D is the number of distinct values. I see no easy way to deduce that 32 bits suffice for the total, apart from N < 2¹⁶.

If parallelising this for n processors, one could let different processors process different residues modulo n.

I considered keeping track of the number of even values, to avoid a scan of half the frequencies, but I think that for most datasets within the given parameters that would yield little advantage.

Answer 2

Ok, I am not going to write your whole algorithm for you, but it can definitely be done faster. So i guess this is what you need to get going:

So you have your list sorted, so there are a lot of assumptions you can make from this. Take for instance the highest value. It wont have any multiples. The highest value that does, will highest value divided by two.

There is also one other very usefull fact here. A multiple of a multiple is also a multiple. (Still following? ;)). Take for instance the list [2 4 12]. Now you've found (4,12) as a multiple pair. If you now also find (2,4), then you can deduce that 12 is also a multiple of 2. And since you only have to count the pairs, you can just keep a count for each number how many multiples it has, and add that when you see that number as a multiple itself. This means that it is probably best to iterate your sorted list backwards, and look for divisors instead.

And maybe store it in some way that goes like [ (three 2's ), (two 5's), ...] ie. store how often a number occurs. Once again, you don't have to keep track of it's id, since you only need to give them the total number of pairs. Storing your list this way helps you, because all the 2's are going to have the same amount of multiples. So calculate once and then multiply.