1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ If you want to apply inclusion-exclusion, you also need count[3.5],count[3.7], count[5.7] and count[3.5.7] just to handle the {3,5,7} case. $\endgroup$ – Hendrik Jan Oct 18 '18 at 17:57
  • $\begingroup$ So does there exist an alternate solution? if so, please mention @HendrikJan $\endgroup$ – Sparsh Kedia Oct 18 '18 at 18:03
  • $\begingroup$ Welcome to Computer Science! This looks like a nice problem. If it comes from an online programming contest or a coding camp, please add a URL. If it comes from a book or a paper, a reference. Besides paying proper attribution to the original source, all those information motivate and help people answer the question faster and better. Please add those information in the question since people and search engine are not expected to look at comments. $\endgroup$ – Apass.Jack Oct 19 '18 at 0:08
  • $\begingroup$ As an optimization, note that you only need to go to intersections of length at most $\log n$. $\endgroup$ – Yuval Filmus Oct 19 '18 at 4:26
  • $\begingroup$ How many primes are there? That number affects the solution a lot. That is one of the reasons why I am asking for the original source. Suppose there are more than 200 of them. ... $\endgroup$ – Apass.Jack Oct 19 '18 at 5:16
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can it be used to find those numbers which do not form a co prime pair with any of the rest of numbers? Like for eg : 2,3,6,10,12 So here 6 and 12 are the required numbers since they do not form a co prime pair at all. $\endgroup$ – Sparsh Kedia Oct 19 '18 at 8:39
  • $\begingroup$ I spoke too soon. "find those numbers which do not form a co prime pair with any of the rest of numbers" is a lot harder. Thinking ... $\endgroup$ – Apass.Jack Oct 19 '18 at 9:02
  • $\begingroup$ That is why I asked for an optimized solution for the original problem. For each element if the complexity is logN then the overall complexity will just be NlogN which will pass $\endgroup$ – Sparsh Kedia Oct 19 '18 at 9:06
  • $\begingroup$ Can you tell me, what to pass? How is that related to the restriction of no more than 10 primes? $\endgroup$ – Apass.Jack Oct 19 '18 at 9:08
  • 1
    $\begingroup$ That competition problem is not hard for me to do. However, since this is an ongoing competition, I will not provide more suggestion before the competition is over. Let me just say all the answers here are far from a valid answer for that competition problem. $\endgroup$ – Apass.Jack Oct 19 '18 at 9:24
-1
$\begingroup$

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.

$\endgroup$

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.