FR_04_14 - Najbliższa pierwsza

[szotrab1337]

Kod ma przekroczono limit czasu, chce mi ktoś powiedzieć co robię źle?
Mi się wydaje, że dla danych wejściowych działa błyskawicznie.

<tu był link>

[rzaba]

Twój kod nie wykonuje się błyskawicznie na przykład dla takiego testu:

100000
9922331
9922331
9922331
… (99997 kolejnych wystąpień liczby 9922331)

Żeby rozwiązać to zadanie, polecam zapoznać się z sitem Eratostenesa.

[szotrab1337]

Czy chodzi o to, że mam zrobić maksymalną tablicę liczb pierwszych (wejście do 10^7) i następnie ją przeszukiwać?
Zamieszczam link do programu w C#, czy w c++ będzie chodziło o wiele szybciej czy to po prostu nie o to chodzi? Proszę o pomoc

<tu był link>

[szotrab1337]

Napisałem nowy kod ale niestety dostaję błąd wykonania (NZEC). Czy może ktoś pomóc i powiedzieć gdzie jest błąd?

<tu był link>

[rzaba]

Dobrze kombinujesz . Ostatni kod, który wkleiłeś, dostaje NZEC ponieważ dla niektórych testów zgłasza wyjątek IndexOutOfRangeException. Jednym z takich testów jest:

1
10000000

Myślę, że powinieneś sobie poradzić z namierzeniem przyczyny. Gdybyś jednak potrzebował pomocy:

Odpowiedź

Rozmiar tablicy tab jest za mały. Według treści zadania, na wejściu może się pojawić n = 10^7. Twoja tablica ma rozmiar ~10^6.

PS
Jeśli chodzi o jakość kodu - polecam przypisać rozmiar tablicy do jakiejś stałej. Twój kod by zyskał na czytelności, i mógłbyś uniknąć kopiowania i wklejania tej samej liczby.

[szotrab1337]

Dziękuję bardzo za pomoc - jest AC. Popełniłem taki głupi błąd

[rzaba]

Powracając jeszcze do kwestii TLE w kodzie, w którym użyłeś sita. Tamten kod przekracza limit czasu ponieważ korzystasz z metody IndexOf, która przeszukuje liniowo całą tablicę. Dla każdego testu, potencjalnie będziesz przechodził kilka(dziesiąt) razy całą tablicę z liczbami pierwszymi. Można to przyspieszyć korzystając z faktu, że tablica z liczbami pierwszymi jest posortowana. Można w tym przypadku skorzystać z wyszukiwania binarnego.

[mccarol]

Witam Forumowiczów,
próbuję rozwiązać to zadanie, chcąc przyspieszyć kod niestety utknęłam, bo sędzia pokazuje błędną odpowiedź. Nie potrafię znaleźć tego błędu. Moje testy program przechodzi. Proszę o pomoc w znalezieniu błędu w kodzie lub o testy, które naprowadzą mnie na błąd.
kod w Javie:
-tu był kod-
Z góry dziękuję

[pawoj20]

wejscie
1
4
prawidlowe wyjscie
3

Co do optymalizacji to moze to jeszcze potrwac

[mccarol]

Bardzo dziękuję za wskazanie błędu.
Poprawiłam go i udało mi się również trochę przyspieszyć kod. Nadal to jednak nie to.
-tu był kod-

[pawoj20]

Prawdopodobnie nie uda sie zejsc z czasem ponizej limitu bez sita Erastotenesa liczonego jeden raz.

[mccarol]

Dziękuję za pomoc. Zadanie zaliczone.