algorithm - Find the number of pairs where the first element is divisible by second element -

suppose, given numbers

8, 7, 6, 5, 4, 3, 2 

you have find pairs (a, b) a appears in list before b, , a%b = 0.

here, such pairs are:

(8, 4), (8, 2), (6, 3), (6, 2), (4, 2) 

is there better algorithm o(n²) ?

you can precompute list of divisors of possible integers in input = o(n^1.5)

after iterate on input, while keeping track of how number worth (i.e. how many pairs form).

for every number in input you'll need iterator on it's divisors, i.e. o(n^1.5)

so total complexity o(n^1.5) n maximum of 100000 , size of input.

class denominators {                                                              public static void main (string[] a) {                                           int maxvalue = 100000;                                                       int[] problemset = {8, 7, 6, 5, 4, 3, 2};                                    system.out.println (new denominators().solve(problemset, maxvalue));     }                                                                              int solve (int[] problemset, int maxvalue) {                                     list<list<integer>> divisors = divisors(maxvalue);                           int[] values = new int[maxvalue + 1];                                        int result = 0;                                                              (int : problemset) {                                                       result += values[i];                                                         (int d : divisors.get(i)) {                                                  values[d]++;                                                             }                                                                        }                                                                            return result;                                                           }                                                                              private list<list<integer>> divisors (int until) {                               list<list<integer>> result = new arraylist<>();                              (int = 0; <= until; i++) {                                               result.add (new arraylist<integer>());                                   }                                                                            (int = 1; * <= until; i++) {                                           (int j = i; j * <= until ; j++) {                                          result.get (i * j).add(i);                                                   if (i != j) result.get (i * j).add(j);                                   }                                                                        }                                                                            return result;                                                           }                                                                         }