Logowanie

Badanie czy liczba jest liczba pierwsza - złożoność

pytanie zadane 8 stycznia 2018 w C i C++ przez marakuja Użytkownik (590 p.)

Witam,
Witam czy można określić złożoność algorytmu sprawdzającego czy liczba jest liczba pierwsza? np. podobnego do tego tutaj:
http://www.algorytm.edu.pl/algorytmy-maturalne/badanie-czy-liczba-pierwsza.html

Pobieramy jedną liczbę, sprawdzamy do sqrt tej liczby. Jak wyznaczyć złożoność, dwa scenariusze? Mógłby ktoś pomóc?

1 odpowiedź

odpowiedź 8 stycznia 2018 przez Jedras Maniak (54,860 p.)

Sprawdź sobie, ile razy wykona się w najgorszym przypadku pętla w funkcji sprawdzającej czy liczba jest pierwsza.

komentarz 8 stycznia 2018 przez marakuja Użytkownik (590 p.)

I w najgorszym bedzie poprawnie?

Podobne pytania

0 głosów

3 odpowiedzi 788 wizyt

Czy liczba jest liczbą pierwszą

pytanie zadane 6 grudnia 2017 w C i C++ przez Newaz Użytkownik (880 p.)

0 głosów

1 odpowiedź 1,109 wizyt

sprawdzenie poprawności kodu programu do sprawdzania czy liczba jest liczbą pierwszą

pytanie zadane 6 listopada 2017 w C i C++ przez mn130496 Gaduła (3,640 p.)

0 głosów

2 odpowiedzi 542 wizyt

Sumowanie przedziałów - mała złożoność

pytanie zadane 18 października 2022 w C i C++ przez Perkol02 Nowicjusz (120 p.)

...