569. Piotruś w Krainie Liczb Pierwszych [BFN2]

[narbej]

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

Nie bardzo rozumiem, co masz na myśli, ale i tak na pewno nie masz racji. Twój program faktycznie daje poprawne wyniki, ale tylko dla [bardzo] niewielkich testów. Na stronie ideone.com, możesz przecież wygodnie testować a nie tylko wklejać swój kod. Zobacz: https://ideone.com/vZ5RE4 <-- twój kod dla małych wartości wyświetlił poprawny wynik, ale wywalił się na “trochę” większym teście - runtime error [błąd wykonania].

Sprawdź i potestuj sam, może ja się pomyliłem i dałem za duży test?

No i oczywiście nie zmieniaj nauczycielki, przecież ja też na pierwszy rzut oka nie widzę błędu w twoim kodzie, a na pewno tam jest, bo tak twierdzi SPOJ - który wcale aż tak zacofany nie jest i tak samo twierdzi ideone.com.

PS
Na drugi rzut oka już jest inaczej, niestety. Twoje sito jest za bardzo dziurawe
Oczywiście to przenośnia, a chodzi bardziej o zbyt mały rozmiar, czy raczej błędy konstrukcyjne.

PS 2
Czy to zadanie nie jest czasami z kategorii wyższej niż łatwe?.

[rosiakstudio]

A jeśli zmiana typu danych na większy nie sprawia, że program przestaje się wywalać to co zmodyfikować?

[mariusz193]

należy popatrzeć na:

linia 6 (niech początek to 2000000000, koniec 2000000100)
linia 8
linia 10
linia 11 (lub lepiej 16)

gdy patrzę na ten program, to linie świecą się na czerwono

[tarpauwatratar]

zmień nauczycielkę od informatyki

Tylko czy nauczycielka znała treść zadania i miała świadomość, jakie zakresy liczbowe występują w zadaniu…

[anim_90]

Hej, zabrałem się za to zadanie, jednak otrzymuję “runtime error”. Z mojej strony implementacja to sito eratostenesa. I tutaj moje pytanie: czy to jest wystarczający algorytm? Czy pułapka jest w jego optymalizacji? Czy też powinienem odejść od tego klasycznego rozwiązania? Dziękuję za pomoc.

[tarpauwatratar]

Jeżeli dobrze zaimplementujesz odpowiednią wersję sita to wystarczy

[leszekrz_53]

Odgrzewam stary kotlet, ale znowu widzę przykład, że tylko C lub C++ zalicza AC.
Ja mam w Python 3 błąd wykonania SIGKILL.
W ideone wszystko ok: https://ideone.com/p7oKeq
(błąd, czy może problemy z zasobami i kompatybilnością serwera Spoj?)
Może mnie proszę ktoś oświecić? @narbej ?

[quenthui]

Na takim teście się wykładasz

1
999900000 1000000000

A to nie są najwyższe dopuszczalne wartości

[leszekrz_53]

Faktycznie…ale na 10x mniejszych wartościach jest TLE 5 sekund, więc i tak nie ma szans.
PS: zmieniłem wersje sita tak, żeby nie było mnożenia wielkich liczb (i*i) ale to nic nie dało.
Brak pomysłów.

[narbej]

Zadanie ma co najmniej 1 zaliczenie w Pythonie.
Nie wiem czy to dobry pomysł?:

Zrób pierwsze zadanie z łatwych i pochwal się (pokaż) kodem. Może wtedy coś wymyślę?

Ps
Czytałeś cały ten wątek? Dobrze że jest środek nocy i nie widać czy się rumienię

[leszekrz_53]

PRIME_T - Liczby Pierwsze rozwiązałem. Tu są niewielkie zakresy liczb więc mniejsze problemy. Ciekawe, że wyszedłem z wersji z modułem Numpy i trochę możę przekombinowaną. Najgorsze, żę Numpy wyklucza użycie PyPy jak dotąd. W końcu uprościłem i z PyPy wyszło 0.38sek a po dodaniu fast i/o 0.17sek. Kod: https://ideone.com/LuHLJA

Co innego z BFN2 - w Krainie Liczb Pierwszych. Zastosowałem Numpy, lepsze sito i udało się dojść do końca zakresu ale jest TLE około 5 sekund na ideone: https://ideone.com/y1IEx5
Niestety PyPy nie lubi Numpy.
Zapisałem się na ideone i po zwiększeniu TL do 15sek dochodze do maks.liczb https://ideone.com/auK2rp oczywiscie z TLE (ale 999900000 1000000000 liczy 7.75s)

[narbej]

SPOJrzyj proszę na listę najlepszych rozwiązań w Pythonie2:

POLSKI SPOJ: test your programming skills on-line

Twoje rozwiązanie nie używa sita. Tworzy listę liczb pierwszych, którą nazywa sieve, ale to raczej nie ten algorytm - możliwe, że się mylę?

W trudniejszym zadaniu, moim zdaniem jest podobnie. Używasz [tworzysz] listę liczb pierwszych ale nie metodą sita. Może poczytaj o sicie na wikipedii?

[leszekrz_53]

Moim zdaniem to jednak są sita, bo tak jak w każdej jego wersji wykreślane są wielokrotności liczb w tabeli i na końcu zostają tylko liczby pierwsze. W sitach sprawdzenie czy n jest liczbą pierwszą odbywa się zawsze od 2 lub 3 niezależnie od n, więc mój pomysł polegał na stworzeniu gotowej tabeli liczb pierwszych, jak zauważyłeś, dla największej z n, czyli sito tylko raz dla n max z danych. Tym sposobem mam gotowca na resztę danych bez ponownego użycia sita.
Te wersje, których używałem są dostępne tu: https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n/3035188#3035188
W BFN2 ma to jakiś sens bo przedziały są duże.
W PRIME_T właśnie niekoniecznie najlepsze będzie sito. Z sitem plasuję się bliżej czołówki peletonu, ale sprawdzę jak będzie bez sita.
… już mam: https://ideone.com/LKobiq trochę szybciej niż z sitem jak podejrzewałem. (0.14sek).
Co do BNF2 w Spyder + Python 3.9 liczenie od 2147483600 do 2147483646 wynik 2147483629 jako l.pierwsza i Elapsed time: 18.27 sek. Sito liczyło od 2 do 2147483646.
Z drugiej strony, metoda bez sita jak w PRIME_T sprawdza samą liczbę 2147483629 w 0.012 sek co wydaje się szybko, ale dla zakresów 10^6 i 120 zestawów to za wolno rzecz jasna.

Tak swoją drogą to Python jest dla takich zagadnień jak BFN2 wolniejszy około 30 razy nie licząc istotnego spowolnienia w I/O. Trudno jest więc w ogóle porównywać kody Pythona i C++ pod względem szybkości działania. Programiści w Pythonie są szykanowani takim doborem zadań gdzie wypadają z powodu TLE. C++ rządzi to wiadomo, ale czy o to tu chodzi?