Determining number of elements divisible by at least one prime of set

Question

I have an array ($|A|\leq 10^6$) of numbers ($A_i\leq10^6$) and a set of prime numbers. I have to find the count of the elements in the array that are divisible by at least one of the numbers in the given set.

For example:

Array: {3,5,7,15,21,143}

Set: {3,5,7}

Output : 5

The numbers are 3(3), 5(5), 7(7), 15(3,5), 21(3,7).

If the array size is $10^6$, an $n^2$ algorithm would time out.

Possible approach: I can preprocess all numbers in the array and store the count of elements each prime factors appear in.

For the example given above : The prime factors are 3,5,7,11,13 and values of the count array will be count[3]=3, count[5]=2, count[7]=2, count[11]=1, count[13]=1.

Can the principle of inclusion and exclusion be applied in this case or is there any other approach to the problem?

Answer 1

One possible approach is to use the GCD algorithm: calculate the GCD of each number in your array with the product of the given primes.

Answer 2

If the number of numbers in the given array is no more than $10^6$, each of which is no larger than $10^6$, and the number of primes is no more than 10, then the way to move forward is apparently the following simplest algorithm in usual situations.

Initiate a boolean array A of False of size 1 plus the maximum of all numbers or just 1000001.
for each given prime number p:
    mark elements at A[p], A[2p], A[3p], etc until the end of array as True.
let count = 0
for each given number n:
    if A[n] is False, add count by 1
return count

The above algorithm is simple to code. It runs very fast since there is no division. It is likely to be faster than all other algorithms when the density of numbers is over 1/10, such as over $10^4$ numbers each of them is smaller than $10^5$, or over $10^5$ numbers each of them is smaller than $10^6$.

The algorithm could be improved if we also know or compute the smallest and the maximal number of all given numbers.

This algorithm will be very inefficient if we just have, for example, two numbers, 1 and $10^6$, and 10 primes numbers. However, it won't need a split of second on a normal computer, still. There is no visible incentive to go for a more efficient algorithm, which will probably be harder to code.

Answer 3

Ok, so first and foremost: If some number X appears multiple times in A, we can calculate the answer for X once and just check the precalculated answer.

So basically, now we have 10^6 distinct numbers. AKA, 1,2,3...10^6. Good! So we just have to calculate the answer for all numbers between 1 and 10^6.

The second observation it's trivial to see that if the divisors set contains repeated numbers we can just erase the repetitions.

So now the divisors set only has distinct elements. Cool! Now a kinda brute force algorithm will work.

For each divisor X we will mark their multiples as "divisible". Please notice the number X has 10^6/X divisors.

You can see the code below of how this works:

#include <iostream>
#define MAX 1000005
///If I already added X to the set
bool already_computed[MAX];
///If the number X is divisible by someone in the set
bool seen[MAX];
int main(){
    ///First and foremost, we are reading the set
    int N;///Number of elements in the set
    std::cin>>N;
    for(int i=0;i!=N;++i){
        int x;
        std::cin>>x;
        ///If we didn't add x yet
        if(!already_computed[x]){
            ///Mark that you checked x
            already_computed[x]=true;
            ///Now I'm going to iterate EVERY single number upto 10^6
            ///I'm just checking the numbers that are divisible by X
            ///Please notice I'm checking 10^6/X numbers.
            int b=x;
            while(b<MAX){
                seen[b]=1;
                b+=x;
            }
        }
    }
    ///Now I'm reading the array
    int M;
    std::cin>>M;
    int answer=0;
    for(int i=0;i!=M;++i){
        int x;
        std::cin>>x;
        ///Notice that we already calculated our answer above :)
        answer+=seen[x];
     }
     std::cout<<answer<<"\n";
     return 0;
}

Here's the example the author gave us in the code's input format:

3
3 5 7
6
3 5 7 15 21 143

Ok, cool. At first glance this may seem like an optimized O(N^2), but it's actually O(N log N).

Proof: $\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...\frac{1}{N}\approx log(N)$

Now multiplying the above equation by N:

$\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+...\frac{N}{N}\approx N\cdot log(N)$

And the below fraction is EXACTLY the complexity of what we are doing in the loop where we insert the numbers contained in the set.

If you are interested in this equation please check the Harmonic Series https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

In my simulations the code above runs in around 30ms even in the worst-case scenarios, so I would say it's pretty efficient to solve the problem mentioned above.

Answer 4

Put all the primes in a sieve, ignoring duplicates. O(n), giving about n / ln n primes.

Put all the numbers in a sieve, counting multiplicity. O(n).

Take each prime in turn, count all multiples and how often they are present, then remove the multiples. The time is n / p, summed over the primes from 1 to n. I think that is O(n) as well.

Answer 5

I think this process might give you the results Step1. know the no of elements Step2. Load the first prime number and check for divisibility. Step3. If the number in the array is divisible replace it with the prime you are dividing else Skip it. Step4. Load the next prime & repeat the process up to last prime in the set. Step5. Output={no of elements that are grater than largest prime number in the set}. I think the program goes like this

#include <stdio.h>#include < math.h> Int main() { Int x[100],y[20],z[100],I,j; Scanf/give x&y; For (i=1;i<=100;i++){ z[i]=x[i]; } For (j=1;j<=20,j++) { For(i=1;i<=100;i++) { z[i]=x[i]%y[j]; If(z[i]==0) { z[i]=y[j]; } else { z[i]=x[i]; } } } j=0; for (i=1;i<=100;i++) { If(z[i]>y[20]) { j++; } } Printf j; return 0; }

Ps:I skipped some syntax & I forgotten some syntax.