Vánoční nadílka Vánoční nadílka
Vánoční akce! Daruj lepší budoucnost blízkým nebo sobě. Až +50 % zdarma na dárkové poukazy. Více informací
Avatar
Jan Michálek:17. listopadu 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. listopadu 14:30
Odpovědět 17. listopadu 14:29
Nemá cenu nic programovat, pokud se to neprogramuje geniálně.
Avatar
patrik.valkovic
Šéfredaktor
Avatar
Odpovídá na Jan Michálek
patrik.valkovic:17. listopadu 15:03

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

Nahoru Odpovědět  +1 17. listopadu 15:03
Nikdy neumíme dost na to, abychom se nemohli něco nového naučit.
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Jan Michálek
Martin Dráb:17. listopadu 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í
+1 bodů
Řešení problému
Nahoru Odpovědět 17. listopadu 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.