Avatar
vajkuba1234
Člen
Avatar
vajkuba1234:

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. listopadu 11:01
Odpovědět 26. listopadu 11:00
No hope, no future, JUST WAR! For world peace Israel must be DESTROYED!
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na vajkuba1234
Jan Vargovský:
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  +1 26. listopadu 11:07
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Jan Vargovský
vajkuba1234:

Ja vim, na to jsem zapomnel :D

Nahoru Odpovědět  -1 26. listopadu 11:09
No hope, no future, JUST WAR! For world peace Israel must be DESTROYED!
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na vajkuba1234
Jan Vargovský:

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  +1 26. listopadu 11:16
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na vajkuba1234
Martin Dráb:

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

Nahoru Odpovědět 26. listopadu 12:09
2 + 2 = 5 for extremely large values of 2
Avatar
Jan Vargovský
Redaktor
Avatar
Odpovídá na Martin Dráb
Jan Vargovský:

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

 
Nahoru Odpovědět 26. listopadu 12:30
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Martin Dráb
vajkuba1234:

Jan Vargovský

maximum 2000000000, typ int.
Editováno 26. listopadu 12:44
Nahoru Odpovědět 26. listopadu 12:42
No hope, no future, JUST WAR! For world peace Israel must be DESTROYED!
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Jan Vargovský
Martin Dráb:

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. listopadu 12:47
2 + 2 = 5 for extremely large values of 2
Avatar
vajkuba1234
Člen
Avatar
Odpovídá na Jan Vargovský
vajkuba1234:

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. listopadu 12:58
Nahoru Odpovědět 26. listopadu 12:57
No hope, no future, JUST WAR! For world peace Israel must be DESTROYED!
Avatar
coells
Redaktor
Avatar
Odpovídá na Martin Dráb
coells:

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  +1 26. listopadu 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.