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

Željko Perić

8y1kVisual 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

8 Replies

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

Arun Potti6d ago
Your recursion is essentially applying the inclusion-exclusion principle, but it creates a new array with Array.Copy on every recursive call and repeats calculations. You can make it faster by iterating over combinations of the primes and avoiding array allocations.

static long Count(long n, long[] primes)
{
    long result = 0;
    int combinations = 1 << primes.Length;
    for (int mask = 1; mask < combinations; mask++)
    {
        long product = 1;
        int count = 0;
        bool valid = true;
        for (int i = 0; i < primes.Length; i++)
        {
            if ((mask & (1 << i)) == 0)
                continue;
            // Avoid overflow and combinations that cannot divide
            // any number <= n.
            if (product > n / primes[i])
            {
                valid = false;
                break;
            }
            product *= primes[i];
            count++;
        }
        if (!valid)
            continue;
        long divisible = n / product;
        if ((count & 1) == 1)
            result += divisible;
        else
            result -= divisible;
    }
    return result;
}
+1
- Željko Perić6d ago
  Thanks for answer.
  0
Željko Perić6d ago
For everyone who wants to download the complete source code, explore advanced optimizations (including CollectionsMarshal and Int128 versions), the project is available at the following link:
periczeljkosmederevo/CountDivisibleNumbers
High-performance C# implementation and benchmarks for counting numbers in a range divisible by given primes using the Inclusion-Exclusion Principle.
0

Željko Perić6d ago

New examples of more optimized code:

using System;
using System.Collections.Generic;
using System.Runtime.InteropServices;

namespace CountDivisibleNumbers
{
    /// 
    /// Provides an ultra-optimized memoized version of the recursive divisibility algorithm,
    /// using the Inclusion-Exclusion Principle with single-lookup caching (via CollectionsMarshal) 
    /// to eliminate redundant calculations and memory allocations.
    /// 
    public static class UltraOptimizedDivisibilityCounter
    {
        // Dictionary for memoization storing precalculated results by key (n, index)
        private static readonly Dictionary<(long n, int index), long> _memo = new();

        /// 
        /// Calculates the count of numbers in the range [m, n] that are divisible 
        /// by any of the numbers in the test array p, utilizing memoization.
        /// 
        /// The lower bound of the range (inclusive).
        /// The upper bound of the range (inclusive).
        /// An array of test numbers for the divisibility check.
        /// The count of divisible numbers in the specified range [m, n].
        /// 
        /// IMPORTANT: No duplicates are allowed, and no mutually divisible numbers are allowed 
        /// (e.g., 4 and 2, or 35 and 5). The input array p must be filtered beforehand 
        /// to ensure correct mathematical results and optimal recursive performance.
        /// 
        public static long CalculateRange(long m, long n, long[] p)
        {
            _memo.Clear();
            long countN = Compute(n, p, 0);
            _memo.Clear();
            long countM1 = Compute(m - 1, p, 0);
            return countN - countM1;
        }

        /// 
        /// Initiates the divisibility calculation for the range [1, n] after clearing the cache.
        /// 
        /// The upper limit of the number range [1, n].
        /// An array of test divisors.
        /// The count of divisible numbers in the range from 1 to n.
        public static long Calculate(long n, long[] p)
        {
            _memo.Clear();
            return Compute(n, p, 0);
        }

        /// 
        /// Core recursive function with memoization implementing the Inclusion-Exclusion Principle 
        /// to count how many numbers from 1 to n are divisible by any number in array p, 
        /// optimized with single-lookup caching via CollectionsMarshal.
        /// 
        /// The upper limit of the number range [1, n].
        /// The array of test divisors.
        /// The current index in the test array.
        /// The count of divisible numbers up to n starting from the given index.
        /// 
        /// IMPORTANT: No duplicates are allowed, and no mutually divisible numbers are allowed 
        /// (e.g., 4 and 2, or 35 and 5). The input array p must be filtered beforehand 
        /// to ensure correct mathematical results and optimal recursive performance.
        /// 
        private static long Compute(long n, long[] p, int index)
        {
            if (index >= p.Length)
                return 0;

            var key = (n, index);

            // SINGLE-LOOKUP SEARCH AND INSERT: Returns a reference to the value in the dictionary.
            // If the key exists, 'exists' is true and we immediately return the cached result.
            // If it does not exist, space is allocated, 'exists' is false, and 'r' becomes a reference 
            // where we directly write the computed value without performing another lookup!
            ref long r = ref CollectionsMarshal.GetValueRefOrAddDefault(_memo, key, out bool exists);
            if (exists)
            {
                return r;
            }

            long countDivisible = n / p[index];
            long term1 = Compute(n / p[index], p, index + 1);
            long term2 = Compute(n, p, index + 1);

            r = countDivisible - term1 + term2;
            return r;
        }
    }
}

using System;

namespace CountDivisibleNumbers
{
    /// 
    /// Provides an optimized recursive implementation of the divisibility counting algorithm
    /// using the Inclusion-Exclusion Principle, without memoization or dictionary lookups.
    /// It directly calculates the number of divisible integers within the specified range
    /// by recursively evaluating products of selected divisors.
    /// 
    public static class UltraOptimizedDivisibilityCounterV2
    {
        /// 
        /// Calculates the count of integers in the range [m, n] that are divisible
        /// by at least one divisor from the specified array p.
        /// Uses the Inclusion-Exclusion Principle to calculate the result directly
        /// for the requested range, avoiding separate calculations for n and m - 1.
        /// 
        /// The lower bound of the range (inclusive).
        /// The upper bound of the range (inclusive).
        /// An array of test divisors, sorted in ascending order.
        /// 
        /// The number of integers in the specified range [m, n] divisible
        /// by at least one divisor from the array p.
        /// 
        /// 
        /// IMPORTANT:
        /// The divisors must be positive, distinct, and pairwise coprime.
        /// No duplicates or divisors sharing common factors are allowed.
        /// The input array p must be filtered beforehand to satisfy these conditions.
        ///
        /// The array should be sorted in ascending order to enable early termination
        /// when a divisor product exceeds the upper bound n.
        ///
        /// Intermediate results are accumulated using Int128 to reduce the risk
        /// of arithmetic overflow during inclusion-exclusion calculations.
        /// The final result is checked when converted to long.
        /// 
        public static long CalculateRange(long m, long n, long[] p)
        {
            if (m > n || n < 1 || p.Length == 0)
                return 0;

            long lower = m <= 1 ? 0 : m - 1;

            Int128 result = 0;

            Accumulate(n, lower, p, 0, 1, true, ref result);

            return checked((long)result);
        }

        /// 
        /// Calculates the count of positive integers in the range [1, n]
        /// that are divisible by at least one divisor from the specified array p.
        /// 
        /// The upper bound of the range (inclusive).
        /// An array of test divisors, sorted in ascending order.
        /// 
        /// The number of integers in the range [1, n] divisible
        /// by at least one divisor from p.
        /// 
        public static long Calculate(long n, long[] p)
        {
            return CalculateRange(1, n, p);
        }

        /// 
        /// Recursively evaluates the Inclusion-Exclusion Principle by generating
        /// products of selected divisors and accumulating their contribution
        /// to the final count.
        ///
        /// Each recursive level selects the next divisor, calculates the number
        /// of multiples of the resulting product within [lower + 1, n],
        /// and alternates between addition and subtraction according to
        /// the Inclusion-Exclusion Principle.
        ///
        /// Products that exceed the upper bound are skipped, allowing early
        /// termination of the current iteration when divisors are sorted
        /// in ascending order.
        /// 
        /// The upper bound of the counting range.
        /// The value immediately preceding the lower bound.
        /// The sorted array of test divisors.
        /// The starting index for selecting the next divisor.
        /// The product of previously selected divisors.
        /// 
        /// Indicates whether the current contribution must be added or subtracted.
        /// 
        /// 
        /// A reference to the Int128 accumulator storing the intermediate result.
        /// 
        private static void Accumulate(
            long n,
            long lower,
            long[] p,
            int index,
            long product,
            bool add,
            ref Int128 result)
        {
            for (int i = index; i < p.Length; i++)
            {
                long divisor = p[i];

                if (divisor > n / product)
                    break;

                long nextProduct = product * divisor;

                long count = n / nextProduct
                           - lower / nextProduct;

                if (add)
                    result += count;
                else
                    result -= count;

                Accumulate(
                    n,
                    lower,
                    p,
                    i + 1,
                    nextProduct,
                    !add,
                    ref result);
            }
        }
    }
}

Benchmark Environment & System Specs:

BenchmarkDotNet Version: v0.15.8
Operating System: Windows 11 (10.0.26300.9818)
Processor (CPU): 13th Gen Intel Core i7-1360P 2.20GHz, 1 CPU, 16 logical and 12 physical cores
SDK / Runtime: .NET SDK 10.0.403 (RyuJIT x86-64-v3)

| Method   | N                | Mean        | Error     | StdDev    | Ratio | RatioSD | Gen0   | Allocated | Alloc Ratio |
|--------- |----------------- |------------:|----------:|----------:|------:|--------:|-------:|----------:|------------:|
| Original | 1000             | 12,491.3 ns | 127.77 ns | 113.26 ns |  1.00 |    0.01 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000             |  1,323.5 ns |   2.05 ns |   1.81 ns |  0.11 |    0.00 |      - |         - |        0.00 |
| Ultra    | 1000             |  1,070.5 ns |   1.90 ns |   1.77 ns |  0.09 |    0.00 |      - |         - |        0.00 |
| UltraV2  | 1000             |    546.5 ns |   0.66 ns |   0.55 ns |  0.04 |    0.00 |      - |         - |        0.00 |
|          |                  |             |           |           |       |         |        |           |             |
| Original | 1000000          | 11,933.5 ns | 201.27 ns | 168.07 ns |  1.00 |    0.02 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000000          |  5,237.7 ns |   8.42 ns |   7.46 ns |  0.44 |    0.01 |      - |         - |        0.00 |
| Ultra    | 1000000          |  4,731.2 ns |   7.62 ns |   6.36 ns |  0.40 |    0.01 |      - |         - |        0.00 |
| UltraV2  | 1000000          |  3,719.8 ns |  17.39 ns |  15.42 ns |  0.31 |    0.00 |      - |         - |        0.00 |
|          |                  |             |           |           |       |         |        |           |             |
| Original | 1000000000000000 | 11,828.7 ns |  87.52 ns |  77.59 ns |  1.00 |    0.01 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000000000000000 |  7,885.1 ns |  14.30 ns |  13.38 ns |  0.67 |    0.00 |      - |         - |        0.00 |
| Ultra    | 1000000000000000 |  6,207.3 ns |   8.51 ns |   7.54 ns |  0.52 |    0.00 |      - |         - |        0.00 |
| UltraV2  | 1000000000000000 |  5,240.6 ns |   6.61 ns |   5.86 ns |  0.44 |    0.00 |      - |         - |        0.00 |

All the best,

Željko Perić

Željko Perić6d ago

After 8 years here is improved version of upper solution that gives currently best performance speed/memory:

using System;
using System.Collections.Generic;

namespace CountDivisibleNumbers
{
    /// 
    /// Provides an optimized memoized version of the original recursive divisibility algorithm,
    /// using the Inclusion-Exclusion Principle with caching to eliminate redundant calculations and memory allocations.
    /// 
    public static class MemoizedOriginalDivisibilityCounter
    {
        private static readonly Dictionary<(long n, int index), long> _memo = new();

        /// 
        /// Calculates the count of numbers in the range [m, n] that are divisible 
        /// by any of the numbers in the test array p, utilizing memoization.
        /// 
        /// The lower bound of the range (inclusive).
        /// The upper bound of the range (inclusive).
        /// An array of test numbers for the divisibility check.
        /// The count of divisible numbers in the specified range [m, n].
        /// 
        /// IMPORTANT: No duplicates are allowed, and no mutually divisible numbers are allowed 
        /// (e.g., 4 and 2, or 35 and 5). The input array p must be filtered beforehand 
        /// to ensure correct mathematical results and optimal recursive performance.
        /// 
        public static long CalculateRange(long m, long n, long[] p)
        {
            _memo.Clear();
            long countN = Compute(n, p, 0);
            _memo.Clear();
            long countM1 = Compute(m - 1, p, 0);
            return countN - countM1;
        }

        /// 
        /// Core recursive function with memoization implementing the Inclusion-Exclusion Principle 
        /// to count how many numbers from 1 to n are divisible by any number in array p.
        /// 
        /// The upper limit of the number range [1, n].
        /// The array of test divisors.
        /// The current index in the test array.
        /// The count of divisible numbers up to n starting from the given index.
        /// 
        /// IMPORTANT: No duplicates are allowed, and no mutually divisible numbers are allowed 
        /// (e.g., 4 and 2, or 35 and 5). The input array p must be filtered beforehand 
        /// to ensure correct mathematical results and optimal recursive performance.
        /// 
        private static long Compute(long n, long[] p, int index)
        {
            if (index >= p.Length)
                return 0;

            var key = (n, index);
            if (_memo.TryGetValue(key, out long cachedResult))
            {
                return cachedResult;
            }

            long countDivisible = n / p[index];
            long term1 = Compute(n / p[index], p, index + 1);
            long term2 = Compute(n, p, index + 1);

            long r = countDivisible - term1 + term2;

            _memo[key] = r;
            return r;
        }
    }
}

Benchmark Environment & System Specs:

BenchmarkDotNet Version: v0.15.8
Operating System: Windows 11 (10.0.26300.9711)
Processor (CPU): 13th Gen Intel Core i7-1360P 2.20GHz, 1 CPU, 16 logical and 12 physical cores
SDK / Runtime: .NET SDK 10.0.403 (RyuJIT x86-64-v3)

| Method   | N                | Mean      | Error     | StdDev    | Ratio | RatioSD | Gen0   | Allocated | Alloc Ratio |
|--------- |----------------- |----------:|----------:|----------:|------:|--------:|-------:|----------:|------------:|
| Original | 1000             | 11.976 us | 0.1862 us | 0.1555 us |  1.00 |    0.02 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000             |  1.276 us | 0.0021 us | 0.0017 us |  0.11 |    0.00 |      - |         - |        0.00 |
|          |                  |           |           |           |       |         |        |           |             |
| Original | 1000000          | 11.435 us | 0.0452 us | 0.0401 us |  1.00 |    0.00 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000000          |  5.213 us | 0.0064 us | 0.0060 us |  0.46 |    0.00 |      - |         - |        0.00 |
|          |                  |           |           |           |       |         |        |           |             |
| Original | 1000000000000000 | 11.533 us | 0.0291 us | 0.0258 us |  1.00 |    0.00 | 6.9275 |   65312 B |        1.00 |
| Memoized | 1000000000000000 |  7.752 us | 0.0072 us | 0.0064 us |  0.67 |    0.00 |      - |         - |        0.00 |

Conclusion:

The evolution from a naive linear scan to an advanced recursive algorithm based on the Inclusion-Exclusion Principle demonstrates how number theory combined with modern .NET optimization techniques (such as dictionary-based memoization) can solve complex computational tasks within microseconds. Benchmark results clearly confirm that the memoized version incurs zero managed memory allocations (0 B) and vastly outperforms the original recursion, ensuring robust, lightning-fast performance even with colossal ranges up to long.MaxValue.

All the best,

Željko Peric

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