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
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.
1 month later
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…
21 days later
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.
3 years later
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:
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?