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
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
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.
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 
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.com7, możesz przecież wygodnie testować a nie tylko wklejać swój kod. Zobacz: https://ideone.com/vZ5RE423 <-- 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.com7.
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?.
A jeśli zmiana typu danych na większy nie sprawia, że program przestaje się wywalać to co zmodyfikować?
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
Tylko czy nauczycielka znała treść zadania i miała świadomość, jakie zakresy liczbowe występują w zadaniu…
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.
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/p7oKeq3
(błąd, czy może problemy z zasobami i kompatybilnością serwera Spoj?)
Może mnie proszę ktoś oświecić? @narbej ?
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.
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ę
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/LuHLJA3
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/y1IEx53
Niestety PyPy nie lubi Numpy.
Zapisałem się na ideone i po zwiększeniu TL do 15sek dochodze do maks.liczb https://ideone.com/auK2rp1 oczywiscie z TLE (ale 999900000 1000000000 liczy 7.75s)
SPOJrzyj proszę na listę najlepszych rozwiązań w Pythonie2:
W trudniejszym zadaniu, moim zdaniem jest podobnie. Używasz [tworzysz] listę liczb pierwszych ale nie metodą sita. Może poczytaj o sicie na wikipedii?
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#30351882
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?
| Topic | Category | Replies | Views | Activity |
|---|---|---|---|---|
| TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 193 | Feb 1 |
| FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 155 | Apr 2 |
| SPOJ.com - Problem ZABAWA pl.spoj.com | Zbiór zadań | 6 | 136 | Jun 23 |
