How many numbers in a range [1-n] are divisible by any of given test numbers

How many numbers in a range [1-n] are divisible by any of given test numbers

This problem is easy to solve with for .. next / for .. each loop and modulo function for divisibility check.

// n range of numbers from 1 to n

// p array of primes for divisibility check

long f(long n, long [] p)

{

long k = 0;

for(long i = 1; i<=n; i++)

{

foreach(long prime in p)

{

if(i%prime==0)

{

k++;

break;

}

}

}

return k;

}

This function works perfect but it is too slow for bigger range of numbers for example [1-100 000 000].

This interesting math problem can be solved by using Set theory and it's Inclusion-exclusion principle.

Example : Find out how many numbers in a range [ 1 - 10 ] are divisible by any of given numbers, {2,3}.

First find out how many numbers are divisible by two, then by three, and at the end by inclusion-exclusion principle

find out how many numbers are divisible by any of those two.

Set N {1,2,3,4,5,6,7,8,9,10} , contains range of numbers to be tested

Set A {2,4,6,8,10} , |A| = 5 , contains numbers divisible by 2

Set B {3,6,9} , |B| = 3 , contains numbers divisible by 3

Set C {2,3,4,6,8,9,10} , |C| = 7 , contains numbers divisible by any of given numbers

|C| = |A| - |A∩B| + |B| , count of divisible numbers

According to the above math theory here is the recursive function that solves the problem.

// n range of numbers from 1 to n

// p array of test numbers for divisibility check

// no duplicates aloved,

// no mutual divisible numbers aloved exmpl : 4 and 2 or 35 5

// q copy of array p from element 1 to k element

// r count of divisible numbers

long f(long n, long [] p)

{

if(p.Length==0)

return 0;

long [] q = new long[p.Length-1];

Array.Copy(p,1,q,0,p.Length-1);

long r = (n/p[0])- (f(n/p[0],q)) + (f(n,q));

return r;

}

This is simple but currently most efficient recursive function written in C#,

that easilly can be used for solving many simillar problems.

Question is :

- Is it possible to write this function in C# differently so that its execution becomes faster ?

All the best,

Author