Koliko je brojeva u opsegu [1, n] deljivo sa bilo kojim zadatim deliocem 

Ovaj problem je lako rešiti pomoću for...next / for...each petlje i modulo funkcije za proveru deljivosti.

// n je opseg brojeva od 1 do n

// p je niz prostih/test brojeva za proveru deljivosti

// nisu dozvoljeni duplikati,

// nisu dozvoljeni međusobno deljivi brojevi, npr: 4 i 2 ili 35 i 5

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;

}

Ova funkcija radi savršeno, ali je previše spora za veće opsege brojeva, na primer za [1 - 100.000.000]. Ovaj interesantan matematički problem može se rešiti korišćenjem teorije skupova i njenog principa uključenja i isključenja.

Primer: Saznajte koliko je brojeva u opsegu [1 - 10] deljivo sa bilo kojim od datih brojeva {2, 3}. Prvo utvrdite koliko je brojeva deljivo sa dva, zatim sa tri, i na kraju pomoću principa uključenja i isključenja saznajte koliko je brojeva deljivo sa bilo kojim od ta dva broja.

• Skup N = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} — sadrži opseg brojeva koji se testiraju.

• Skup A = {2, 4, 6, 8, 10\}, |A| = 5 — sadrži brojeve deljive sa 2.

• Skup B = {3, 6, 9}, |B| = 3 — sadrži brojeve deljive sa 3.

• Skup C = {2, 3, 4, 6, 8, 9, 10}, |C| = 7 — sadrži brojeve deljive sa bilo kojim od datih brojeva.

|C| = |A| - |A∩B| + |B| — ukupan broj deljivih brojeva.

Prema gornjoj matematičkoj teoriji, evo rekurzivne funkcije koja rešava problem:

// n je opseg brojeva od 1 do n

// p je niz test brojeva za proveru deljivosti

// nisu dozvoljeni duplikati,

// nisu dozvoljeni međusobno deljivi brojevi, npr: 4 i 2 ili 35 i 5

// q je kopija niza p od elementa 1 do k-tog elementa

// r je broj deljivih brojeva

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;

}

Ovo je jednostavna, ali trenutno najefikasnija rekurzivna funkcija napisana u C#-u, koja se lako može koristiti za rešavanje mnogih sličnih problema.

Pitanje je:

• Da li je ovu funkciju moguće napisati drugačije u C#-u tako da njeno izvršavanje postane brže?

Odgovor na ovo pitanje leži u eliminisanju suvišnih rekurzivnih ponavljanja primenom memoizacije (keširanja međurezultata). Uvođenjem rečnika (Dictionary) za pamćenje već izračunatih vrednosti za parove (n, index), drastično se smanjuje broj rekurzivnih grana, čime algoritam postaje znatno brži.

Evo te napredne, optimizovane verzije:

// Rečnik za keširanje međurezultata (memoizacija) koji pamti izračunate vrednosti po ključu (n, index)

private static Dictionary<(long n, int index), long> _memo = new Dictionary<(long n, int index), long>();

/// <summary>

/// Pokreće proračun deljivosti za opseg [1, n] uz prethodno čišćenje keša.

/// </summary>

/// <param name="n">Gornja granica opsega brojeva [1, n].</param>

/// <param name="p">Niz testnih delitelja.</param>

/// <returns>Broj deljivih brojeva u opsegu od 1 do n.</returns>

public static long Calculate(long n, long[] p)

{

    _memo.Clear();

    return Compute(n, p, 0);

}

/// <summary>

/// Osnovna rekurzivna funkcija sa memoizacijom koja primenjuje princip uključenja i isključenja 

/// za brojanje koliko je brojeva od 1 do n deljivo sa bilo kojim brojem iz niza p.

/// </summary>

/// <param name="n">Gornja granica opsega brojeva [1, n].</param>

/// <param name="p">Niz testnih delitelja.</param>

/// <param name="index">Trenutni indeks u testnom nizu.</param>

/// <returns>Broj deljivih brojeva do n počevši od datog indeksa.</returns>

/// <remarks>

/// VAŽNO: Duplikati nisu dozvoljeni, kao ni međusobno deljivi brojevi 

/// (npr. 4 i 2, ili 35 i 5). Ulazni niz p mora biti prethodno filtriran 

/// kako bi se osigurali tačni matematički rezultati i optimalne performanse rekurzije.

/// </remarks>

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;

}

BenchmarkDotNet Rezultati merenja performansi

Testiranje je izvršeno u sledećem sistemskom okruženju:

• Sistem: Windows 11 (10.0.26300.9711)

• Procesor: 13th Gen Intel Core i7-1360P 2.20GHz, 1 CPU, 16 logičkih i 12 fizičkih jezgara

• SDK: .NET SDK 10.0.403 (RyuJIT x86-64-v3)

Zaključak

Benchmark rezultati jasno potvrđuju da memoizovana verzija ne alocira nikakvu dodatnu keš memoriju (0 B) i višestruko nadmašuje originalnu rekurziju.

Za sve koji žele da preuzmu kompletan izvorni kod i istraže napredne optimizacije projekat je dostupan na sledećem linku:

https://github.com/periczeljkosmederevo/CountDivisibleNumbers

Ili na linku u tabeli ispod CountDivisibleNumbers open source.zip

Sve najbolje,

Autor