Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Diskuze: Pomalá doba běhu programu.

Aktivity
Avatar
Jan Michálek:17.11.2018 14:29

Zdravím,

mám napsat program do školy, který vypíše všechny prvočísla od a do b (vstupy od uživatele). Program jsem napsal.

#include <iostream>

using namespace std;

int main()
{
    cout << "Zadejte interval:" << endl;
    int a,b,promenna;
    cin >> a >> b;

    if ((cin.fail())||(a>b)){
        cout << "Nespravny vstup." << endl;
        return 0;
    }

    for (int i=a;i<=b;i++){
        for (int j=2; j<=b;j++){
            if (i<j){
                   break;
            }
            else {
                promenna = i % j;
                if ((promenna == 0) && (i != j)){
                    break;
                }
                if ((promenna == 0) && (i == j)){
                    cout << i << endl;
                }
                }
            }
            }

    return 0;
}

Problém spočívá v tom, že musí běžet maximálně 1 sekundu. Pokud na vstup zadám hodnoty

a = 1999999900 b = 2000000000

Tak strašně program běží pomalu. Chápu že to je asi tím, že každou hodnotu děli od 2 do velikosti hodnoty a
Nechápu, ale jak docílit toho, aby to fungovalo lépe. Už si s tím lámu delší dobu hlavu a vůbec nevím jak na to. Proto zde píši. Byl by tu někdo tak hodný mi poradit?

Mnohokrát děkuji.

Editováno 17.11.2018 14:30
Odpovědět
17.11.2018 14:29
Nemá cenu nic programovat, pokud se to neprogramuje geniálně.
Avatar
Odpovídá na Jan Michálek
Patrik Valkovič:17.11.2018 15:03

Stačí ti kontrolovat čísla jen do odmocniny z a.

Nahoru Odpovědět
17.11.2018 15:03
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Jan Michálek
Martin Dráb:17.11.2018 17:18

Stačí ti kontrolovat čísla jen do odmocniny z a

Přesněji, do odmocniny z i. Snížíš tím počet testů cca na odmocninu z b pro každé číslo v intervalu. A to se velmi vyplatí (a je to zřejmě důvod, proč ti program běží tak pomalu).

Dále můžeš:

  • opravit horní mez vnitřního cyklu tak, abys tam nemusel mít podmínku na i < j (tam přijde ta odmocnina z i v zásadě), čímž ušetříš jednu podmínku (podmínky jsou drahé pro CPU... ač tady to bude celkem dobře řešit predikce),
  • testovat pouze dvojku a lichá čísla (snížíš počet testů cca na polovinu).
Akceptované řešení
+20 Zkušeností
+2,50 Kč
Řešení problému
Nahoru Odpovědět
17.11.2018 17:18
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.