569. Piotruś w Krainie Liczb Pierwszych [BFN2]

[Adrian_Kuegel]

Zadanie: http://www.spoj.pl/SPOJPL/problems/BFN2/
--
Witam.

Napisałem program, Wydaje mi się, że nie jest on jakoś super niezoptymalizowany, a dostaję błąd o przekroczeniu limitu czasu. Z tego co widzę nie jestem jedynym, który ma ten problem. Rozmiar także ok.

A w zadaniu w końcu jest podany limit aż 13 sek.

Napisałem go w C++, wykorzystując vectory z STL-a. Na próbę usunąłem z programu vectory (i nie działa poprawnie), by sprawdzić, czy to one tak obciążają, ale także przekroczyłem czas.

Hmm, czy tylko mi się wydaje, czy coś jest nie tak? Możecie na to rzucić okiem?

Pozdrawiam

[m_sasinowski1]

Nie patrzyłem na Wasze rozwiązania, natomiast moje przechodzi, co prawda prawie 12 sek. Ale używa powiedzmy "standardowych" algorytmów oraz w jednym miejscu jest bardzo nieoptymalny.

[mima_sof]

Standardowy, to np. algorytm wykorzystujący metodę "sito eratostenesa" pozwalający dość szybko przesiać pewien zbiór liczb - uzyskując (w nim) w efekcie tylko liczby pierwsze.

Pozdrawiam!

[jpfarias]

Sprawdź, czy program nie zapętla sie w nieskończoność dla jakiegoś szczególnego przypadku, czasem właśnie z tego powodu przekracza się czas.

[piastlis]

Znalazłem błąd.Nie chodziło o program tylko o założenia.Dla tego zakresu potrzebne są liczby pierwsze do 46337 a ja policzyłem do 4639.Ale "czeski błąd" to też błąd

-- N lip 19, 2015 10:45 pm --

Problem rozwiązany.Ale przy okazji mam jeszcze jedno pytanie.Starałem się napisać ten program najlepiej jak potrafię czyli by był możliwie najszybszy.Uzyskałem czas 3.02 sek i skończyły mi się pomysły jak go przyspieszyć.Najlepszy wynik z listy to 0.16sek.Jak można ten problem rozwiązać prawie 20 razy szybciej???

-- Pn lip 20, 2015 11:43 pm --

He he .Okazało się że nie jestem tak durny jak myślałem.Samo przejście z cout>> na printf() pozwoliło na redukcję czasu do 0.33 sek!!!Jak na razie mam dość tego problemu ale wrócę do niego za jakichś czas.Może uda się zmniejszyć czas o rząd wielkości...

[narbej]

Dzień dobry panie Narbej.
Piszę do pana z pytaniem/prośbą odnośnie zadania :
http://pl.spoj.com/problems/BFN2/1
otóż
od kilku dni próbuję rozwiązać to zadanie, najpierw po prostu
sprawdzając każdą liczbę czy jest pierwsza (jednakże to jest
zdecydowanie za wolny sposób i łatwo przekroczyć limit czasowy),
następnie sitem erastotenesa, jednakże nie jestem w stanie utworzyć tak wielkiej tablicy (błąd pamięci dla 2 miliardów).
Pomyślałem więc, że wystarczy utworzyć tablicę tak wielką jak jest przedział np.
dla
przedziału 8 15 wystarczy nam (15-8)+1 elementowa tablica. Jednakże
wtedy nie potrafię wskazać liczb, które należy wykreślić, postanowiłem
więc wpisywać te liczby z przedziału do tablicy i na tej podstawie je
jakoś wykreślać jednakże i ten sposób zawiódł.
A co pan ma do tego?
No nie ukrywam, że widziałem, że jest pan "najlepszy" w tym zadaniu. To
nie chodzi o to, akurat, że tylko jest pan najlepszy, tylko udziela się
pan dosyć często na forum, zatem jest pan aktywny - co za tym idzie -
może będzie pan w stanie odczytać tę wiadomość szybciej niż tydzień po
jej napisaniu.
Czego od pana oczekuję?
- Podpowiedzi
czy jest jakiś inny algorytm na liczby pierwsze? Jeśli nie to czy jednak należy to zrobić w jakiś sposób sitem?
Mam nadzieję, że się pan nie pogniewa, przez tę wiadomość, (jeśli tak - proszę nie odpisywać).

Pozdrawiam serdecznie, Jack.

PS - Edit1

Jedyne wzmianki odnośnie tego zadania (z tego co widzę) znajdowały się na starym forum, które aktualnie jest niedostępne.

[mariusz193]

a gdzie odpowiedź, chyba nie zawiedziesz pokładanego w tobie zaufania?

[narbej]

Jedyne wzmianki odnośnie tego zadania (z tego co widzę) znajdowały się na starym forum, które aktualnie jest niedostępne.

Pytający nie natchnął się na powyższy wątek, więc "podałem go na tacy". W wątku powyższym są odpowiedzi na pytania.

PS
Poczta prywatna służy do prywatnej wymiany myśli, między dobrymi znajomymi. W innym wypadku bardzo łatwo może zostać potraktowana jako tzw niechcianą pocztą, a nie prywatną i nawet ma to swoją nazwę i nie zmieni to nazywanie mnie najlepszym i inne cuda niewidy.. Tym bardziej, że wcale nie jestem najlepszy.

[redysz]

Tym bardziej, że wcale nie jestem najlepszy.

Nie dość, że najlepszy to i najskromniejszy

[tarpauwatratar]

W gruncie rzeczy kwestia kryterium.

Czasowo rozwiązanie narbeja jest najlepsze.
Pamięciowo jest chyba przeciętne (nie wczytywałem się, ale widzę rozwiązania zajmujące 3x mniej miejsca).
W rankingu ogólnym narbej jest na tą chwilę trzeci z wynikiem 1329.01 pkt.
I w oczach wielu uchodzi za autorytet na polskim SPOJu, a może nawet eksperta i najlepszego algorytmika w Polsce

A którym kryterium się kierować wybierając sobie adresata PW - to już zostawiam wszystkim do samodzielnego osądzenia.

[adambek]

Serduszko za PS

[tarpauwatratar]

Czy ktoś zrobił to testami pierwszości? Jeżeli tak to proszę o jakieś wskazówki, najlepiej na PW.

Moje próby kończą się źle dla około 800 liczb, które mój algorytm uznaje za pierwsze wbrew prawdzie. Około, bo od wczoraj rozkładam liczby na czynniki pierwsze i porównuje wynik z moim programem - na razie jestem przy 1672719217, która wg mnie jest pierwsza a wg http://www.numericana.com/data/carmichael.htm 1672719217 = 13 * 29 * 1553 * 2857.

PS
Tablica z przypadkami szczególnej troski zaszyta w kodzie oczywiście jest rozwiązaniem, ale najlepiej, aby w ogóle nie było stablicowanych wyników a jeżeli już muszą być to wolałbym maks 100 przypadków a nie ok 800.

PS2
Rozwiązanie “wincyj testów dla danej liczby” nie jest rozwiązaniem tylko proszeniem się o TLE. Czas ok. 13 sekund mi nie przeszkadza, ale są pewne granice

PS3
Brak odp na PW - być może nikt nie stworzył lepszego algo wg tej konecpcji niż ze stablicowaniem “problematycznych” testów? W każdym razie takie rozwiązanie przechodzi z nie tak złym czasem ok. 7 sek.

[manjaro]

Tak na logikę to samo wypisanie na wyjściu wszystkich liczb pierwszych z przedziału 1- 10^9 zajmie więcej czasu niż 0.1s Więc nie wiem skąd takie kosmiczne wyniki

[mariusz193]

Tak na logikę to samo wypisanie na wyjściu wszystkich liczb pierwszych z przedziału 1- 10^9 zajmie więcej czasu niż 0.1s Więc nie wiem skąd takie kosmiczne wyniki

przecież nie masz wypisywać wszystkich liczb pierwszych - maksymalna długość przedziału to tylko milion
oczywiście, gdyby dla któregoś testu były naprawdę użyte maksymalne wartości podane w zadaniu (czyli 150 razy przedział o długości miliona), to takie czasy byłyby niemożliwe

[manjaro]

No tak ja to wiem, ale jak znam spoja to pewnie jest ze 100 przypadków testowych i w tym takie od 1 do max zakresu

[tarpauwatratar]

Nie wiem ile jest plików testowych, natomiast jak najbardziej może się trafić t = 150 i maksymalne wartości L oraz U. Niemniej wciąż istnieje ograniczenie na różnice tych liczb.

[rosiakstudio]

Witam, zrobiłem sobie zadanko o nazwie jak w temacie. Najpierw wylało mi Segmentation_fault, a teraz SIGABRT. Nie mam pojęcia co one oznaczają, pomimo dołączonego linku do wikipedii. Program śmiga, aż miło nawet dla dużego zakresu. Czas wystarcza i pamięć nie jest przekroczona. Co ciekawe nawet moja nauczycielka od informatyki nie może znaleźć przyczyny. Liczę na was

Ideone.com

[mariusz193]

zmień nauczycielkę od informatyki

[rosiakstudio]

Musiałbym szkołę zmienić, a tu mi dobrze :c

[rosiakstudio]

Dodam, że przykre jest to, iż wyniki są poprawne, a spoj nie wiem czy to przez zacofanie często lubi nie przyjąć.