Determine the number of elements that is divisible by a prime number in an array

I have an array (|A|≤10^6) of numbers (not guaranteed to be distinct) and a set of prime numbers. For each of the prime numbers, I want to know how many numbers in the first array are divisible by this prime number. For example:

Array = {5 5 7 10 14 15}

Set = {2 3 5 7 11}

result:2:2; 3:1; 5:4; 7: 2; 11:0

Brute force by using nested loops works, but is there a faster way?

• Does the set of primes include ALL of them until some maximum one? Jan 2, 2021 at 18:47
• There are faster ways, and whether they are applicable depends on exact constraints you have (e.g. running time and an upper-bound on the numbers).
– user114966
Jan 2, 2021 at 20:06
• Yes including all of them. Jan 2, 2021 at 23:00
• [input] not guaranteed to be distinct is it specified to be monotonically increasing? Sep 30, 2021 at 6:23

Yes if the number of integers and primes is large. Sort the primes in ascending order. Count the number of divisible numbers and remove prime factors until the numbers are all larger than the square of the smallest remaining primes. Now the remaining numbers are all primes. Sort them and check which ones are in the list of primes, in linear order.

This works as long as most primes are greater than the square root of the largest number.

• This sounds a lot like the sieve of Eratosthenes. Jun 2, 2021 at 5:55
• It’s a bit related. Jun 2, 2021 at 6:22
• How does Sort the primes help? With remove prime factors, numbers get smaller: is until the numbers are all larger than… intended? Sep 30, 2021 at 6:38
• "Sort the primes": It's much more likely that a number is divisible by a small prime, so checking for numbers divisible by 2, 3, 5 will tend to make the remaining numbers smaller. Sep 30, 2021 at 7:53

If both lists, let's call them A,P, are sorted as it appears to be:

• Whenever you find A[i] divisible by P[j] replace it by A[i]/P[j]

• If a number A[i] reaches 1 or become smaller than P[j] exclude it from further checks

• A draft Pseudo code would be:

i=j=0;

Repeat
{
While (A didn't finish) {
If (A[i] mod P[j] == 0) {
C[j]++;
A[i]=A[i]/P[j];
If(A[i]≤P[j]) remove A[i];
//endif}
i++;
//endwhile}
j++;
i=0; //or startup mark
//endRepeat
} Until ( A or P ends)

If the equal values are dense (say if the number of distinct values is less than a quarter of the array size), it could be worth to sort and determine the multiplicities. If they are sparse, sorting could be counterproductive.

This said, counting the divisors for a value does not help counting those of other values. So for every value, there is not much better than trying all divisors in turn and stop when the quotient gets too small.

Depending on the distribution of numbers, it could be advantageous to try the divisors in some order rather than another. This needs to be tested experimentally.

If you know that some divisors are rarely met, it could be useful to try the GCD with the product of the rare factors to eliminate them quickly.

OP asked: Given numbers $$A_i$$, and a prime $$P$$, determine for each $$p \leqslant P$$ how many of the numbers $$A_i$$ are divisible by $$p$$.

set counter for each $$p$$ to $$0$$.
remove all $$A_i ≤ 1$$
for $$p = 2, 3, 5, 7, \ldots$$ as long as $$p \leqslant P$$
iterate through values $$A_i$$.
if $$A_i < p^2$$
$$A_i$$ is prime
if $$A_i ≤ P$$ increase counter for $$A_i$$
remove $$A_i$$
if $$A_i$$ is divisible by $$p$$
increase counter for $$p$$
divide $$A_i$$ by $$p$$ until it is not divisible by $$p$$
if $$A_i = 1$$ then remove $$A_i$$

Some time will be saved compared to brute force because we eliminate all entries $$A_i < p^2$$ quite quickly.

We can save more time if there are many entries $$A_i \geqslant p^2$$: If we have removed all factors 2, then the numbers divisible by $$p$$ are $$p^2$$, $$p^2 + 2p$$, $$p^2 + 4p$$ etc. If the number of $$A_i$$ where $$p^2 \leqslant A_i \leqslant p^2 + 2kp$$ is much larger than $$k$$, then we can put all the $$A_i$$ into a hash table and look up the multiples of $$p$$ in the hash table, which will be faster than division if there are many numbers in that range.