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ę
[Algorytm] Liczba pierwsza najbliższa i większa od n
- Althorion
- 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
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 — .
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 — .