NOVINKA! E-learningové kurzy umělé inteligence. Nyní AI za nejlepší ceny. Zjisti více:
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze: Narocnost programu

V předchozím kvízu, Online test znalostí C++, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
vajkuba1234
Člen
Avatar
vajkuba1234:26.11.2016 11:00

Zdravim, do skoly jsem vypracoval program na prvocisla, avsak doba behu programu je omezena na 1 vterinu.
Pri zadani intervalu na vstupu:

1999999900 2000000000

program bezi strasne moc dlouho, tedy vice nez 1s.

Mohli byste mi, prosim, poradit duvod?
Nize zasilam kod.

Dekuji za rady :)

#include <iostream>

using namespace std;

bool jePrvocislo(int n)
{
    if (n <= 2)
        n = 2;
    return (n >= 2);
}

void vypisPrvocisla(int min, int max)
{
    for (int i = min; i <= max; i++)
    {
        for (int j = 2; j <= i; j++)
        {
            if (!(i % j) && (i != j))
                break;

            if (j == i)
                cout << i << endl;
        }
    }
}

int main(void)
{
    int min, max;

    cout << "Zadejte interval:" << endl;
    cin >> min >> max;

    if (!cin.fail())
    {
        if (!jePrvocislo(min) || min > max)
        {
            cout << "Nespravny vstup." << endl;
            return 0;
        }

        vypisPrvocisla(min, max);
    }
    else
    {
        cout << "Nespravny vstup." << endl;
        return 0;
    }

    return 0;
}

PS: Bylo to psano na posledni chvili, takze pokud byste meli vyhrady ke kodu, sem s nimi. :)

Editováno 26.11.2016 11:01
Odpovědět
26.11.2016 11:00
No hope, no future, JUST WAR!
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na vajkuba1234
Jan Vargovský:26.11.2016 11:07 
bool jePrvocislo(int n)
{
    if (n <= 2)
        n = 2;
    return (n >= 2);
}

Nezkoumal jsem zatím zbytek, ale tohle nevím jestli je k smíchu nebo k pláči :D

 
Nahoru Odpovědět
26.11.2016 11:07
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Jan Vargovský
vajkuba1234:26.11.2016 11:09

Ja vim, na to jsem zapomnel :D

Nahoru Odpovědět
26.11.2016 11:09
No hope, no future, JUST WAR!
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na vajkuba1234
Jan Vargovský:26.11.2016 11:16

Jinak nejnaivnější řešení je tohle:

bool jePrvocislo(int n)
{
        if (n <= 1)
                return false;

        for (int i = 2; i <= sqrt(n); i++)
                if (n % i == 0)
                        return false;

        return true;
}
 
Nahoru Odpovědět
26.11.2016 11:16
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na vajkuba1234
Martin Dráb:26.11.2016 12:09

Jak moc velký může být ten interval, kde máš hledat ta prvočísla?

Nahoru Odpovědět
26.11.2016 12:09
2 + 2 = 5 for extremely large values of 2
Avatar
Jan Vargovský
Tvůrce
Avatar
Odpovídá na Martin Dráb
Jan Vargovský:26.11.2016 12:30

Řekl bych, že celá 32b čísla, ale jestli nezvládl tohle, tak nevím jestli chtěli eratosthenovo síto nebo podobné věci :)

Akceptované řešení
+20 Zkušeností
+2,50 Kč
Řešení problému
 
Nahoru Odpovědět
26.11.2016 12:30
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Martin Dráb
vajkuba1234:26.11.2016 12:42

Jan Vargovský

maximum 2000000000, typ int.
Editováno 26.11.2016 12:44
Nahoru Odpovědět
26.11.2016 12:42
No hope, no future, JUST WAR!
Avatar
Martin Dráb
Tvůrce
Avatar
Odpovídá na Jan Vargovský
Martin Dráb:26.11.2016 12:47

No, myslel jsem to tak, že by Erastotenes mohl být v určitých případech rychlejší, než zkoušet číslo po číslu (resp. zkoušet všechna lichá čísla v intervalu). Případně kombinace obojího.

Nahoru Odpovědět
26.11.2016 12:47
2 + 2 = 5 for extremely large values of 2
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Jan Vargovský
vajkuba1234:26.11.2016 12:57

Zadani znelo pouze vypsat prvocisla v zadanem rozsahu a osetrit vstupy. Nic vic, ale to sito urcite zkusim. Pokud byste meli nejake dalsi tipy, rad se neco priucim. :)
Martin Dráb

Editováno 26.11.2016 12:58
Nahoru Odpovědět
26.11.2016 12:57
No hope, no future, JUST WAR!
Avatar
coells
Tvůrce
Avatar
Odpovídá na Martin Dráb
coells:26.11.2016 18:12

V tomhle případě potřebuješ cca 105 kroků, to v C nejsou ani milisekundy, Eratosthenes bude vždy efektivnější.

 
Nahoru Odpovědět
26.11.2016 18:12
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 10 zpráv z 10.