Zadanie - Liczby pierwsze

pytanie zadane 2 sierpnia 2016 w SPOJ przez Steefler Nowicjusz (180 p.)

Cześć wszystkim,

wczoraj rozpocząłem zabawę ze SPOJem i rozwiązałem zadanie Liczby pierwsze. Problem polega na tym ,że mój kod działa, tzn kompiluje się i dla wszystkich liczb zwraca prawidłowe wyniki jednakże sędzia na SPOJu twierdzi inaczej. Piszę w Visual 2013. Sprawdziłem zgodnie z zaleceniami wszystkie ramki, ify itd i nie widzę żadnego błędu. W programie na standardowym wejściu to użytkownik podaje liczby, tak się teraz zastanawiam czy program czasem nie powinien sam tych liczb losować?

Dzięki za jakąkolwiek wskazówkę! :)

komentarz 2 sierpnia 2016 przez Mr. Szanowny Bywalec (2,180 p.)

SPOJ sam poda na wejście swoje liczby więc rób to tak jakby ktoś sam miał to wpisać czyli: cin>>.

Przydałby się link do tego zadania, aby ludzie sami nie musieli go szukać i zachęcisz ludzi by choć trochę się zainteresowali tym pytaniem - niby szczegół ale wygodny. Trochę kodu też nie zaszkodzi.

Jeśli chodzi o nie przyjęcie programu przez spoj jest pełno możliwości - za dużo czasu może się wykonywać, nie przetestowałeś tego na krytyczne, negatywne sytuacje itd. Ale na tym polega SPOJ by wymusić upraszczanie, usprawnianie i znajdowanie lepszych rozwiązań.

2 odpowiedzi

odpowiedź 2 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)
wybrane 2 sierpnia 2016 przez Steefler

Najlepsza

Zakomentuj tylko ten pierwszy cout i będzie AC.

cout << "Wprowadz ilosc danych" << endl;

Ciekawy algorytm ale niestety bardzo wolny. Można go zoptymalizować i w sumie może będzie nawet całkiem dobry. Wystarczy dodać warunek w pętli liczenia dzielników

 if (liczba%j == 0)
            {
                licznik_dzielnikow++;
                if (licznik_dzielnikow >2)
                break;
            }

komentarz 2 sierpnia 2016 przez Steefler Nowicjusz (180 p.)

Dziękuję bardzo za pomoc! :) czas z 2,9 do 0,63!

komentarz 2 sierpnia 2016 przez manjaro Nałogowiec (37,390 p.)

Można jeszcze jedną optymalizację dodać aby dzielniki sprawdzać jedynie do pierwiastka liczby a nie całej liczby. Bo jak nie ma dzielników do pierwiastka to dalej już nie będzie.

odpowiedź 2 sierpnia 2016 przez Porcupine Nałogowiec (31,560 p.)

Nie, losować na pewno nie powinien. Więcej bez kodu trudno pomóc ;)

komentarz 2 sierpnia 2016 przez Steefler Nowicjusz (180 p.)

Tutaj wrzucam maina. http://pastebin.com/DvKCh7Y1

wcześniej mam zadeklarowane część zmiennych.

tutaj link do zadania http://pl.spoj.com/problems/PRIME_T/

komentarz 2 sierpnia 2016 przez Porcupine Nałogowiec (31,560 p.)

1) Twój program nie działa dla liczby = 1

2) Twój program jest ogólnie bardzo wolny i można go zoptymalizować co najmniej w 2 miejscach.

3) Nie powinieneś wypisywać zbędnych komunikatów w stylu "Podaj liczbę".
4) Popracuj nad stylem pisania, entery, trochę przesadzasz z tymi enterami ;)

komentarz 2 sierpnia 2016 przez Steefler Nowicjusz (180 p.)

1) No przy wpisaniu 1 wyskakuje komunikat NIE, bo 1 nie jest liczbą pierwszą.

2) Nie bardzo rozumiem co rozumiesz poprzez optymalizacje tak prostego kodu -> dopiero się uczę a na uczelni w zasadzie nie wspominają o tym

3) już poprawiłem.

4) Czy kod nie powinien być przede wszystkim przejrzysty? Pytam bo każda taka wskazówka na pewno pomoże :)

komentarz 2 sierpnia 2016 przez Porcupine Nałogowiec (31,560 p.)

1) Ok, nie uruchamiałem, tylko tak mi się wydawało jak widziałem ten warunek ==2
2)

Weźmy, że sprawdzasz czy 140 jest liczbą pierwszą, będziesz lecieć: 1, 2, 3, 4, 5, ..., 140? Skoro wiadomo, że każda liczba parzysta większa od 2, nie jest liczbą pierwszą.
Weźmy liczę 139 - wiesz już, że jest to liczba nieparzysta, więc po co masz sprawdzać podzielność 2,4,6,8,...,138 skoro liczba nieparzysta nie będzie podzielna przez liczbę parzystą?

3) :)
4) Więcej enterów != przejrzysty