1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Does the set of primes include ALL of them until some maximum one? $\endgroup$
    – HEKTO
    Jan 2, 2021 at 18:47
  • $\begingroup$ 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). $\endgroup$
    – user114966
    Jan 2, 2021 at 20:06
  • $\begingroup$ Yes including all of them. $\endgroup$ Jan 2, 2021 at 23:00
  • $\begingroup$ [input] not guaranteed to be distinct is it specified to be monotonically increasing? $\endgroup$
    – greybeard
    Sep 30, 2021 at 6:23

4 Answers 4

0
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ This sounds a lot like the sieve of Eratosthenes. $\endgroup$
    – RonJohn
    Jun 2, 2021 at 5:55
  • $\begingroup$ It’s a bit related. $\endgroup$
    – gnasher729
    Jun 2, 2021 at 6:22
  • $\begingroup$ How does Sort the primes help? With remove prime factors, numbers get smaller: is until the numbers are all larger than… intended? $\endgroup$
    – greybeard
    Sep 30, 2021 at 6:38
  • $\begingroup$ "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. $\endgroup$
    – gnasher729
    Sep 30, 2021 at 7:53
0
$\begingroup$

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)

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ can't you just edit your answer of Jan 2, instead of posting a second answer? (not complaining, just asking) $\endgroup$
    – user206904
    Nov 2, 2021 at 0:13
  • $\begingroup$ Divisibility is not demanded for every primes, but for specific ones. $\endgroup$
    – user16034
    Sep 19, 2022 at 11:11
  • $\begingroup$ @user206904 They are different answers. $\endgroup$
    – gnasher729
    Oct 19, 2022 at 14:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.