algorytm, liczba pierwsza

b) Sito Eratostenesa, opisane na początku zadania, służy do wyznaczania wszystkich liczb
pierwszych z zadanego przedziału [2, N].


Podaj w wybranej przez siebie notacji (lista
kroków, schemat blokowy lub język programowania) inny algorytm, który sprawdza, czy
podana liczba naturalna L > 1 jest liczbą pierwszą.


 Zauważ, że chcemy sprawdzać
pierwszość tylko liczby L, natomiast nie jest konieczne sprawdzanie pierwszości liczb
mniejszych od L. Przy ocenie Twojego algorytmu będzie brana pod uwagę jego złożoność
czasowa.


Specyfikacja:
Dane: Liczba naturalna L >1.
Wynik: Komunikat Tak, jeśli L jest liczbą pierwszą, komunikat Nie w przeciwnym razie.




1.wprowadź L
2. jeżeli L % 1 !==0   lub    L <2   wyświetl komunikat " zła liczba " i przejdź do kroku 1.
3. oblicz sqrt(L)
4.  wprowadź    i = int
5. i = 2
6.   for ( i = 2; i <= sqrt (L) ; i++)   zrób krok 7.
7.  if   L % i == 0   jeżeli tak -> zakończ pętle    i wyświetl komunikat " nie " ,
 jeśli nie : wyświetl komunikat " tak "
8. zakończ algorytm






witam, zastanawiam się jaka forma pisania algorytmu jest do " przyjęcia" na maturze.
co sądzicie o mojej formie ? ?
czy jest dozwolone takie użycie ?
mieszanie angielskiego, polskiego i c++ ??

Według mnie to nie ważne jak nazwane, ważne, że dobrze działa i jest wydajne. Na olimpiadach informatycznych nie jest sprawdzane jak coś zapisałeś tylko czy to działa wydajnie, więc podejrzewam, że podobnie jest na maturze.

właśnie nie mam pewności :(
stąd chciałbym aby wypowiedział się ktoś kto zna się na tym .

Do liczb pierwszych jeżeli ograniczenie wielkości kodu nie przeszkadza, to stwórz sobie gotową tablicę liczb pierwszych - tzn. wygeneruj ją sobie wcześniej i wklej do pliku z kodem. Później już tylko sprawdzasz, czy liczba mieści się w tablicy (przeszukiwaniem binarnym masz złożoność logarytmiczną), ewentualnie możesz wygenerować liczby do sqrt(n) i sprawdzać podzielność testowanej liczby. Algorytmów jest wiele :) Do wygenerowania tablicy można użyć sita.

Jak umiejętnie stworzysz tablicę to nie będziesz musiał używać przeszukiwania jej i złożoność zmaleje :P

Jak umiejętnie stworzysz tablicę to nie będziesz musiał używać przeszukiwania jej i złożoność zmaleje :P

Wiesz o tym, że ten sposób zużywa bardzo dużo pamięci? Jeżeli mieści się limicie to żaden problem, ale ogólnie to jest zły pomysł.

Ale czasami jedyne rozwiązanie. Na maturze nie wiem czy da się to zrobić tak jak mówiłeś. Szczerze mówiąc przy zadaniach algorytmicznych nie spotkałem się jeszcze, żeby komuś pamięci brakło.

to moze klucz zobaczcie :
Za podanie poprawnego algorytmu sprawdzającego:
- czy L jest podzielna przez i = 2,.., L – 1
– 3 punkty,
- czy L jest podzielna przez i = 2,.., ⎢ L / 2⎥   <- pierwiastek
⎣ ⎦
– 4 punkty,
- czy L jest podzielna przez i = 2,.., ⎢ L⎥ <- pierwiastek
⎣ ⎦
– 6 punktów.


czyli raczej pomysł z utworzeniem tablicy jest słaby ;x ?


no ale mozemy wrócmy tak do mojego algorytmu, czy nadaje się na maturę czy też nie ?
jakieś uwagi ??