[Algorytm] Liczba pierwsza najbliższa i większa od n

ReaSSe
Użytkownik
Użytkownik
Posty: 1
Rejestracja: 3 cze 2013, o 17:23
Płeć: Mężczyzna
Lokalizacja: Polska

[Algorytm] Liczba pierwsza najbliższa i większa od n

Post autor: ReaSSe »

Witam,
ostatnio zacząłem majstrować trochę z algorytmami i natknąłem się na takie zadanie: Napisz algorytm, który dla podanej liczby n znajdzie najbliższą większą od niej liczbę pierwszą (chodzi o schemat blokowy). Jeżeli ktoś mógłby rozpisać o co chodzi i jak go zrobić to z góry dziękuję
Awatar użytkownika
Althorion
Użytkownik
Użytkownik
Posty: 4541
Rejestracja: 5 kwie 2009, o 18:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 9 razy
Pomógł: 662 razy

[Algorytm] Liczba pierwsza najbliższa i większa od n

Post autor: Althorion »

Program realizujący ten algorytm ma przyjmować na wejściu liczbę naturalną \(\displaystyle{ n}\) i zwracać taką liczbę pierwszą \(\displaystyle{ p}\), że będzie większa od \(\displaystyle{ n}\) i możliwie mała, tak na przykład dla czwórki powinna zostać zwrócona piątka, dla siódemki jedenastka itp.

Sensowne wydają się dwa podejścia — trzymanie w pamięci tablicy liczb pierwszych i generowanie odpowiedzi z niej (wyszukiwanie binarne po prostu) bądź branie kolejnych liczb większych od niej (można ignorować nieparzyste na przykład) tak długo, aż któraś w jakimś teście nie okaże się pierwsza. Najprostszym testem pierwszości jest sprawdzanie podzielności przez wszystkie liczby mniejsze od \(\displaystyle{ \lfloor\sqrt{n}\rfloor}\), najlepiej dostosowanym do zadania — .
ODPOWIEDZ