[C][SPOJ] Liczby Pierwsze. Kłopoty z optymalizacją.

pytanie zadane 18 marca 2016 w C i C++ przez marcin_w Gaduła (3,190 p.)
edycja 22 marca 2016 przez marcin_w

Witam wszystkich, mam problem z optymalizacją kodu który dotyczy tego zadania:

http://pl.spoj.com/problems/PRIME_T/

Nie chodzi mi o to, że jest błąd w kodzie tylko o to aby skrócić czas wykonywania programu. Próbowałem różnych sposobów, jednak SPOJ pokazuje czas, który wynosi 2,33 s i 2,34 s. Patrząc na zgłoszenia innych czas ten jest bliski 0.Wiem że, są tablice, algorytmy Eratostenesa itd. Nawet próbowałem jakoś przerobić je na potrzeby zadania(ze zrozumieniem), lecz nie udało mi się.

Dlatego chciałbym prosić o podanie wskazówek, dzięki którym czas wykonania będzie krótszy.

4 odpowiedzi

odpowiedź 18 marca 2016 przez ZakosiliMiNeta Nałogowiec (30,870 p.)

odpowiedź 18 marca 2016 przez MetGang Nałogowiec (34,360 p.)

1. Algorytm w osobnej funkcji.

2. Warunki specjalne - liczba jest równa 1 lub jest parzysta (bez 2) -> return true;

3. Iteracja i+=2 dzięki czemu ominiemy sprawdzanie parzystych w pętli.

4. constexpr :p

komentarz 18 marca 2016 przez jpacanowski VIP (101,940 p.)

1. Algorytm w osobnej funkcji.

CO ??!

komentarz 18 marca 2016 przez MetGang Nałogowiec (34,360 p.)

Przenieść kod z maina do innej funkcji, którą potem wywołasz z jakąś liczbą żeby zachować porządek i uczyć się dobrych nawyków.

komentarz 18 marca 2016 przez marcin_w Gaduła (3,190 p.)

Nie mogę zastosować zmiennej logicznej zwracającej true/false ponieważ w zadaniu ma zwracać tekst TAK lub NIE. Ja piszę w C a contexpr dotyczy C++.

komentarz 18 marca 2016 przez MetGang Nałogowiec (34,360 p.)

No to constexpr najzwyczajniej sobie odpuść. To że coś jest w funkcji nie znaczy, że musi zwracać bool. No ale skoro ma zwracać napis to zastosuj tylko 2, 3 punkty.

komentarz 18 marca 2016 przez marcin_w Gaduła (3,190 p.)

Wiem że funkcja niekoniecznie musi zwracać bool. No ale skoro ma zwrócić napis to musiałbym nadać funkcji typ char tak ?

komentarz 18 marca 2016 przez MetGang Nałogowiec (34,360 p.)

No poniekąd char* musiałaby zwracać, ale pewien nie jestem czy by coś nie rypło. Póki co zastosuj inne punkty, a potem ewentualnie rozpatrz przeniesienie.

komentarz 18 marca 2016 przez marcin_w Gaduła (3,190 p.)

Nie rozumiem tego czyżby mój warunek if(n <2) był wolniejszy od tego, który ty podałeś ? Dlaczego mam iterować pętle i+=2 skoro pierwsza pętla służy do określania liczby testów a druga dotyczy liczby ? Pogubiłem się.