FR_02_13 - Liczby (nie)pierwsze

Ok, napisałem sobie tester, który idzie "na głupa" od liczby a do liczby b, sprawdza czy są pierwsze i jak nie to wydłuża przedział "niepierwszości". Wszystkie powyższe wyniki są prawidłowe. Tak więc muszę chyba sobie przejść po wszystkich (od 0 0 do 4000000 4000000) kombinacjach par i sprawdzić później wyniki.

Przecież chcę to zrobić u siebie na komputerze. Jakie TLE? Robi mi to nawet teraz (już około a=2, b=2miliony) i idzie dalej w poszukiwaniu pary, która daje błędny wynik. Szacunkowo skończy za kwartał.

Tu masz rację... nie mam pojęcia jak on działa. Po prostu skoro czasem mi się wywala wcześniej, a jak zmienię coś w programie to właśnie na jedenastym to podejrzewałem, że informuje o pierwszym błędnym teście. Przechodzi najpierw wszystkie?
"Problemsetterem" z chęcią zostanę, ale chcę trochę więcej problemów przed tym zrobić.

Póki jest mogę go używać bez względu na Twoje zdanie (to stwierdzenie nie miało zabrzmieć arogancko jak coś). Natomiast zastanawiam się czemu w szczególnie w takim celu w jakim go użyłem jest według Ciebie złe? Skomentowałem treść zadania w komentarzu co mi się wydaje logiczne.

A teraz wracając. Mam kilka pytań (do Ciebie i kilkunastu innych osób co zrobiły to zadanie), które może mnie nakierują:
Czy testy są w pełni zgodne z matematyką i 0 oraz 1 jest niepierwsze? Czyli czy wynik testu
0 0 to:
1,
zaś 0 1 to:
2?

Czy są jakieś inne szczególne przypadki, które trzeba specjalnie obsłużyć? Nie wiem... np. przedział typu [liczba_pierwsza,ta_sama_liczba_pierwsza] (jak dla mnie powinno tu być 0) lub na końcu (na końcu ostatniej liniii wyjścia) nie może być entera. Bo nie mogę dojść gdzie mogę mieć błąd.

Ogólnie mój algorytm:
od a do b wyliczam sitem liczby pierwsze (oczywiście sitem od 2 do pierwiastka z b) i mierzę długość przedziału od liczba_pierwsza+1 do następna_liczba_pierwsza-1 włącznie. Zapamiętuję zawsze najdłuższy i voila. Powinno działać, a jest błędna odpowiedź. Próbowałem też wyniki tablicować (wektorem oczywiście) i nawet też da się zmieścić w czasie, ale wynik błędny.

No tak. Doceniam to i dziękuję za to. "A teraz wracając ..." rozumiałem jako: ok to w takim razie szukajmy dalej przyczyny. Faktycznie w teście było 0 0 to mogłem o to nie pytać, ale 0 1 nie było

Czemu (pytam o "poprawna"?) Może tu coś nie rozumiem. Opisuję jak robię na przykładzie:
Załóżmy, że mam przedział [150,200]. Wynajduję liczby pierwsze w tym przedziale, czyli:
151. Aktualnie najdłuższy przedział 151-150=1
157. Aktualnie najdłuższy przedział156-152+1=5 (bo 152,153,154,155,156)
163. Aktualnie najdłuższy przedział 162-158+1=5
167. Aktualnie najdłuższy przedział nadal5 (bo 166-164+1=3)
173. Dalej 5
179. Dalej5
181. Dalej 5
191. Aktualnie najdłuższy przedział190-182+1=9
193. Dalej 9
197. Dalej9
199. Dalej 9
200. Dalej9 (sprawdzam oczywiście koniec przedziału z ostatnią znalezioną liczbą pierwszą)
Odpowiedź to 9.
Czy tu gdzieś się mylę? Liczby niepierwsze to wszak liczby właśnie z przedziału między kolejnymi liczbami pierwszymi (prócz 0 i 1 rzecz jasna).
Oczywiście wszystkie liczby pierwsze od 2 do 4000000 mam policzone raz przed rozpoczęciem powyższej zabawy (i przed przyjęciem informacji o ilości testów).

Widzę komentarze pod Liczby pierwsze i jak najbardziej można się załamać (np. wrzucaniem kodu). Jakby ludzie używali tego systemu do komentowania właśnie treści zadania (to co ja zrobiłem) myślę, że wyglądało by to lepiej. W trudnych myślę nie przepadnie. Gdyby jednak to dla osób, które natkną się na ten wątek:

Czy istnieje wzór wyznaczający liczby pierwsze?1

Super, dzięki (odpowiedziałeś oczywiście wcześniej, ale warto mieć to napisane tak stricte)

Może źle się wyraziłem, ale chyba właśnie to robię. Odpowiedź 9 to jak najbardziej wielkość największego podzbioru kolejnych liczb naturalnych niepierwszych w przedziale obustronnie domkniętym (w tym przypadku [150,200]).

Czy się mylę?

U mnie dla a==b jak najbardziej będzie też 0 lub 1
Co do szybkiego wyszukiwania to masz rację, że można drzewem szybciej, aczkolwiek chwilowo mam błędną odpowiedź i nadal nie wiem dlaczego. oczywiście wiem, że dlatego, że mam coś źle, ale wydaje mi się, że algorytm, prócz prędkości, jest poprawny i tu pytanie... czy tak jest?

---Edit---
Znalazłem omówienie tego zadania na stronie fraktala (nie jest to łatwe). Ostatniego akapitu jednak nie rozumiem:

Przy zapytaniach będziemy szukać wartość maksymalną w przedziale. Należy tylko liniowo rozpatrzyć początkową lewą część przedziału (liczb niepierwszych w tym przedziale może być co najwyżej 147).

Dlaczego tylko początkową lewą część przedziału? Nawias mi nie wyjaśnia. Ja bym zrobił tak: przeszukujemy cały przedział od lewej, chyba że napotkamy 147 to już dalej nie trzeba.
Chyba, że o to właśnie chodziło (ale jeśli tak to trochę niejasno napisane)

nadal jednak interesuje mnie rozwiązanie zagadki błędnej odpowiedzi w moim sposobie.

Kiedyś spróbuję zrobić z tym drzewem, choć bardziej mnie interesuje co jest źle u mnie. Oto kod:
http://ideone.com/540Gkz10

jak nikt nie dojdzie to za jakiś czas skasuję.

Dzięki za wyjaśnienie. Szkoda, że nie dostaje się informacji o wszystkich błędach (jak w zadaniach punktowych).

PS. mój czas nie wydaje mi się najgorszy, a mogę go łatwo przyspieszyć dla dużych danych (dodając warunek, że jeżeli range>2100000 to podaj wynik 147).

Odpowiedź znam... nie rozumiem w Twojej wypowiedzi po prostu jednej części.

Ok... to w sensie kiedy byłby przypadek (dla jakiego przykładowego ciągu), że liczba po lewej (tutaj 5) byłaby odpowiedzią? W sensie po co mi w ciągu ta piątka? Może już z powodu godziny nie rozumiem
Stąd było pytanie o omówienie innego przykłądu.

Dzięki za odpowiedź.

Kolejny raz na tym forum rozmywamy się co do celowości tego co robię. Wytłumaczę by nie było nieporozumień:

Tobie zależy na poprawnym wykonaniu zadaniu na spoja - super, cudownie. Taki masz cel i ok. Chciałbym byś nie mierzył innych swoją miarą. Mój cel jest całkiem inny:
Wchodzę na spoja by znaleźć ciekawe zagadki i sobie je rozwiązać, by się czegoś nauczyć (najczęściej z matematyki). Na drugim miejscu mam to czy dostanę AC czy nie (choć finalnie AC jest potwierdzeniem tego czy dobrze zagadkę rozwiązałem). Wielokrotnie potrafię rozwiązać zadanie (jak to zadanie z prostokątami), ale o wiele bardziej interesuje mnie niejasne matematyczne twierdzenie. Dopiero jak się uporam z twierdzeniem, które na amerykańskiej stronie brzmi "By stwierdzić, czy można zmieścić jeden prostokąt w drugi wystarczy poniższy wzór" - i to twierdzenie jest błędne (co sam potwierdzasz) bo sam wzór nie jest wystarczający, to dopiero rozwiążę sobie to zadanie na spoju poprawnie co jest banalne.

Podobnie... umiem rozwiązać to zadanie sposobem na jaki mnie nakierowałeś (i za to jak najbardziej dziękuję). Natomiast na drugim miejscu mam rozwiązanie tego zadania i otrzymanie AC. Spoj to tylko serwis, którego jutro może nie być. Znalazłem natomiast ciekawą zagadkę - mam program, który dla wszystkich wymyślonych przeze mnie (wielu) par dostaje błędną odpowiedź i się zastanawiam gdzie się wywala. Chcę tę zagadkę rozwiązać przede wszystkim. Jak już dojdę gdzie jest błąd (nie dostanę błędnej odpowiedzi tylko tle) to sobie (albo i nie - w zależności jak będzie mi się chciało) przepiszę ten program tak by dostać AC. Schemat jest prosty więc pewnie go dostanę.

Inaczej pisząc: nawet jakbym zrobił zadanie drzewem, dostał AC (co jest dla mnie nieważne) to i tak bym ten temat założył by dojść czemu w tym rozwiązaniu mam błąd. Gdzie on jest? To jest dla mnie fascynujące. To jest też rozwijające. Ku temu założyłem wątek.

To tak by wyjaśnić swój sposób rozumowania i właśnie dlatego taka propozycja:

Kolejność jest taka: najpierw uzyskaj AC, a potem baw się optymalizacjami, ulepszaczami i przyśpieszeaniem swojego programu. W tym wypadku wiesz jak zrobić program - drzewo maximów + zwykłe sito + wzbogacenie tabeli liczb pierwszych.

do mnie nie przemawia.

Mam nadzieję, że rozumiesz
Nie chciałem uzyskać AC (nie w pierwszej kolejności oczywiście) - tylko znaleźć błąd w tym rozwiązaniu, by się czegoś nauczyć. Po to założyłem wątek.

Więc jeżeli chodzi o zdanie:

Jeżeli chodzi o twój zamieszczony program, to czy warto szukać tam błędu?

skoro po to założyłem wątek by znaleźć właśnie w nim błąd... to nie wiem czy warto szukać tam błędu