Choose jour language!

---

|

5. Neparan broj delilaca -rešenje

I način: Metoda grube sile

Ovaj način podrazumeva da se ispituju svi brojevi redom na intervalu od a i b. Kroz posebnu funkciju se za svaki taj broj odredi koliko ima delioca i onda ako je taj broj neparan, brojač koji je inicijalizovan na 0 svaki put kad se naiđe na broj koji ima neparan broj delioca, poveća za 1. Rešenje:

#include <iostream>

using namespace std;
/*
Primer 1
Ulaz
3 12
Izlaz
2
Pojašnjenje primera: Delioci brojeva od 3 do 12 su sledeći:
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1,2,3,4,6,12
Vidimo da ukupno dva broja (4 i 9) imaju neparan broj delilaca
*/


uint64_t broj_delilaca(uint64_t a)
{
    uint64_t br=0;
    for(uint64_t d=1; d<=a; d++)
    {
        if(a%d==0)
        {
      //      cout <<d<<endl;
            br++;
        }
    }
    return br;
}
int main()
{
    uint64_t a,b,br=0;
    cin>>a>>b;

    /*Menja tekući broj na intervalu od a do b*/
    for(uint64_t i=a; i<=b; i++)
    {
        uint64_t b=broj_delilaca(i); //Izračunava broj delilaca za tekući broj
        if(b%2 != 0) //Ako je broj delioca neparan
        {
            br++; //Povećava brojač za 1
        }
    }

    cout<<br;
    return 0;
}

---

Ovo rešenje je dosta neefikasno za veće vrednosti koje po uslovu zadatka mogu da budu i do 2¹⁵

Znatno efikasnije rešenje je prikazano u nastavku:

---

Varijanta rešenja II: Funkcija potpun_kvadrat

Ovo rešenje se zasniva na činjenici da samo "Potpuni kvadrati imaju neparan broj delioca.
Prosti brojevi imaju samo dva delioca 1 i sam taj broj, npr. delioci broja 7 su 1 i 7, dakle, to je dva, što znači paran broj.
Ostali brojevi koji nisu potpuni kvadrati imaju takođe paran broj delioca. Na slici 1. se mogu uporediti brojevi 12 i 16. Prvi nije potpun kvadrat i može se videti da pored 1 i 12, obojeno narandžasto postoje parovi delioca čiji proizvod daje vrednost 12. To su npr 2 i 6(plavo), 3 i 4 (zeleno). Dakle uvek je paran broj delioca. Ya razliku od nepotpunih kvadrata, kao što je npr. broj 16, može se uočiti da skoro svi delioci imaju svoje parove delioca kao i kod prethodnog slučaja, čiji proizvod daje vrednost 16, međutim delioc 4 bi bio sa samim sobom u paru, tj. 4*4=16. S obzirom da taj delioc računamo samo jednom, može se zaključiti da potpuni kvadrati imaju neparan broj delioca. Ovo je detaljnije objašnjeno u lekciji: Prosti brojevi i faktorizacija.
​

Slika 1: Određivanje delioca brojeva. Nepotpun i potpun kvadrat.

U nastavku je prikazano rešenje koji umesto funkcije koja za neki broj određuje broj delioca, imamo funkciju koja vraća dali ili ne je tekući broj "potpun" kvadrat. U glavnoj funkciji se kroz petlju menja tekući broj za ispitivanje na intervalu od a do b. Brojač će se povećavati samo u slučajevima da se naiđe na broj koji je potpun kvadrat. Rešenje je dato u nastavku:

#include <iostream>
#include<cmath>
using namespace std;
/*
Primer 1
Ulaz
3 12
Izlaz
2
Pojašnjenje primera: Delioci brojeva od 3 do 12 su sledeći:
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
7: 1, 7
8: 1, 2, 4, 8
9: 1, 3, 9
10: 1, 2, 5, 10
11: 1, 11
12: 1,2,3,4,6,12
20: 1,2, 4,5,10, 20
16: 1 2 4 8 16
Vidimo da ukupno dva broja (4 i 9) imaju neparan broj delilaca
*/

/*Funkcija koja ispituje da li je broj a potpun kvadrat*/
bool potpunKvadrat(uint64_t a)
{
    bool rez=false; //Pretpostavimo da nije potpun kvadrat
    if(a>0){
        uint64_t b=sqrt(a);
        rez=(b*b==a);//logicki izraz cija se vrednost dodeljuje promenljivoj b
    }
    return rez;
}
int main()
{
    uint64_t a,b,br=0;
    cin>>a>>b;
   /*Menja tekući broj i na intervalu od a do b sa korakom 1*/
    for(uint64_t i=a; i<=b; i++)
    {
        /*Proverava da li je potpun kvadrat*/
        if(potpunKvadrat(i))
        {
            br++;
        }
    }

    cout<<br;
    return 0;
}

Zaključak

Korišćenje petlje od a do b je neefikasno, pogotovo kada je opseg velik (do 10¹⁵). Rešenje sa proverom svakog broja bi bilo presporo.Umesto toga, treba koristiti matematički pristup, da bi se direktno izračunao broj potpunih kvadrata u opsegu. Evo ispravljenog rešenja:

---

Varijanta 3: Potpuno optimizovano rešenje

Ovde postoji samo glavna funkcijaOptimizovano rešenje u main funkciji:

• Učitavanje ulaznih vrednosti: Učitavaju se vrednosti a i b.
• Pronalaženje prvog i poslednjeg potpunog kvadrata:
  • ceil(sqrt(a)) daje prvi kvadratni koren veći ili jednak a.
  • floor(sqrt(b)) daje poslednji kvadratni koren manji ili jednak b.
• Brojanje potpunih kvadrata:
  • Ako je prvi kvadratni koren manji ili jednak poslednjem kvadratnom korenu, razlika između njih (plus jedan) daje broj potpunih kvadrata u opsegu a do b.

#include <iostream>
#include <cmath>

using namespace std;


int main() {
    uint64_t a, b, br = 0;
    cin >> a >> b;

    // Pronalaženje prvog i poslednjeg potpunog kvadrata u opsegu
    uint64_t prviKvadrat = ceil(sqrt(a));
    uint64_t poslednjiKvadrat = floor(sqrt(b));

    // Brojanje potpunih kvadrata između a i b
    if (prviKvadrat <= poslednjiKvadrat) {
        br = poslednjiKvadrat - prviKvadrat + 1;
    }

    cout << br << endl;

    return 0;
}

Zaključak

Ovaj kod je efikasan i rešava problem koristeći matematički pristup umesto iteracije kroz veliki opseg brojeva, što ga čini pogodnim za rad sa velikim brojevima do 10¹⁵