Initially you should calculate frequency of each number of array.
Let us consider for now that the number be z where
z = p1p2p3 … *pk where count of distinct primes is equal to k. Now for calculating numbers present in array and also divisible by z , you have to just iterate through multiples of z whose complexity is logz(100000).
Now any number less than or equal to 100000 can be represented as a product of at max primes.
(2 X 3 X 5 x 7 x 11 x 13 > 100000). So you can perform recursion and find all possible products of primes.The maximum depth of recursion would easily fit in the time limit.