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?

  • $\begingroup$ Does the set of primes include ALL of them until some maximum one? $\endgroup$ – HEKTO Jan 2 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$ – Dmitry Jan 2 at 20:06
  • $\begingroup$ Yes including all of them. $\endgroup$ – Curious student Jan 2 at 23:00

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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