How many numbers 1 - n are divisible by a range of primes

Željko Perić

8y995Visual Basic .NET

Hello, there was interesting simple math problem I have recently solved :

- How many positive integers in a range 1 to n are divisible by at least one of given primes ?

Here is the recursive function that solves the problem :

// n range of numbers from 1 to n
// p array of primes for divisibility check
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;
}

My question is :

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

All the best,

Željko Peric

3 Replies

Know the answer? Post it — somebody with the same question will find it here.

Dharmraj Thakur8y ago
Compare this once...
static void Main(string[] args)
{
    long[] rng = { 3, 5 };
    var result = FindNums(20, rng);
    Console.ReadKey();
}
public static string FindNums(long n, long[] rng)
{
    StringBuilder result = new StringBuilder();
    for (int i = 1; i < n; i++)
    {
        if (rng.Where(m => m > 0 && (i % m == 0)).Count() > 0)
        {
            result.Append(i).Append(",");
        }
    }
    return result.ToString();
}
+1
Željko Perić8y ago
Solution given by Dharmraj Thakur
is mathematically correct,
but it can't be accepted as answer because it is way too slow.

exmpl:
long n = 100 000 000 - range of numbers 1 - 100 000 000
long [ ] p = new p[3]{5,7,11} - prime numbers for divisibility check 5 7 11
long r = 37662339 divisible numbers counted, this is correct result
execution time is 44106,0756 milliseconds with linq and
execution time is 43275,0199 milliseconds with stringbuilder

It is even slower than this solution that do the same thing with
for..next.../for...each loop and modulo function, as solution that uses linq library
execution time is 11911,5324 milliseconds
// 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;
}
And far too slow comparing to the proposed
final solution given at question above with recursive function and
execution time 0,4598 milliseconds.

Anyway thanks for correct solution,
All the best
Željko Peric.
0
Dharmraj Thakur8y ago
You can do it without recursive using linq
static void Main(string[] args)
{
    long[] rng = { 3,5 };
    var result = FindNums(20, rng);
    Console.ReadKey();
}

public static List<int> FindNums(long n, long[] rng)
{
    List<int> result = new List<int>();
    for (int i = 1; i < n; i++)
    {
        var res = rng.Where(m => m > 0 && (i % m == 0));
        if (res.Count() > 0)
        {
            result.Add(i);
        }
    }
    return result;
}
+1