Determine the number of elements that is divisible by a prime number in an array
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.