• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Liczby Pierwsze - SPOJ Jak uzyskać czas 0.00?

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
+2 głosów
325 wizyt
pytanie zadane 29 kwietnia 2018 w C i C++ przez Kamil Paradowski Użytkownik (620 p.)
edycja 30 kwietnia 2018 przez Kamil Paradowski
Witam, próbuję rozwiązać problem na polskim SPOJ z jak najlepszym czasem.

http://pl.spoj.com/problems/PRIME_T/

Mój kod wygląda następująco - (UPDATE : problem został rozwiązany, nie chce psuć zabawy Innym, więc wykasowalem swój kod).

Uzyskuję czas 0.01... Jednak chciałbym mieć 0.00, bo widzę, że jest to możliwe. Co mógłbym poprawić w tym kodzie, aby mógł działać jeszcze szybciej?

Pozdrawiam :)

3 odpowiedzi

+1 głos
odpowiedź 29 kwietnia 2018 przez Knayder Nałogowiec (37,660 p.)
edycja 29 kwietnia 2018 przez Knayder
Zmienić sposób iterowania po tablicy.
Zacznij od środka. Jeżeli liczba na środku jest większa niż to czego szukasz. To znaczy że liczba której szukasz, jest w pierwszej połowie tablicy. W przeciwnym wypadku po prawej.
Teraz analogicznie zrób z połową tej tablicy. Jeżeli wartość która jest na środku jest większa, to liczba jest z prawej, jeżeli mniejsza, to z lewej. Itd. Aż do znalezienia liczby:

O O X O O O O
            ^
Mniejsza
=============================
O O X o o o o
    ^
Większa
=============================
o o X o o o o
       ^
Oto twoja liczba.
=============================
O <- jakaś liczba
X <- Szukana liczba
o <- odrzucona liczba

Narysowałem ci jeszcze jeden przykład:
https://i.imgur.com/U7ZUrBC.jpg
W ten sposób, znalazłem liczbę, tylko 4 porównaniami. Twoim sposobem, musiałbym zrobić 9.
+1 głos
odpowiedź 30 kwietnia 2018 przez monika90 Pasjonat (22,940 p.)
edycja 30 kwietnia 2018 przez monika90

Zamiast funkcji użyj tablicy, czyli LUT.

const bool is_prime[10001] =
{
   0,0,1,1,0,1,0,1,0,0,0,1, //itd... aż do 10000
};

Oczywiście nie pisz tego ręcznie, tylko napisz program który taką tablicę wygeneruje. (w C++ można taką tablicę wygenerować w czasie kompilacji)

Teraz by sprawdzić czy liczba jest pierwsza wystarczy zamienić () na []

       if (is_prime[number])
            printf("TAK\n");
        else
            printf("NIE\n");

 

Można też, jak się chce, w jednym bajcie upakować informację o ośmiu liczbach. To pozwoli lepiej wykorzystać pamięć podręczną, ale czy zwiększy to wydajność - nie wiadomo.

komentarz 30 kwietnia 2018 przez Kamil Paradowski Użytkownik (620 p.)
Udało mi się już rozwiązać mój problem implementując parę poprawek, między innymi fast I/O. Wcześniej też robiłem tablice typu bool i przypisywałem im wartości logiczne (np. Przy sicie Eratostenesa), jednak w tym przypadku chyba niepotrzebnie straciłbym te 9900 bajtów
–1 głos
odpowiedź 29 kwietnia 2018 przez Benek Szeryf (90,570 p.)
Warunek else if w is_prime jest bez sensu i zabiera czas. Ponadto kod nie robi tego, co nakazuje tresc zadania. Powinienes przeszukac liczby w zakresie 2..10000.
komentarz 29 kwietnia 2018 przez Kamil Paradowski Użytkownik (620 p.)
Jak to? Przecież nie ma nigdzie napisane, że muszę znaleźć konkretne liczby pierwsze, tylko muszę skorzystać z testu pierwszości.

https://pl.wikipedia.org/wiki/Test_pierwszo%C5%9Bci

Moim zdaniem jak najbardziej wykonuje to o co mnie proszono w zadaniu.
komentarz 30 kwietnia 2018 przez Aisekai Nałogowiec (42,210 p.)
Nie jest napisane, że masz sprawdzić wszystkie liczby ale jest napisane coś takiego:

"n - liczba testów n<100000, w kolejnych liniach n liczb z przedziału [1..10000]" więc musiałbyś uzupełnić kolejne liczby pierwsze, mniejsze od 10000 do tej tablicy.

Po drugie, tak jak Knayder napisał musiałbyś wszystkie wrzucić do posortowanej struktury danych i wyszukiwaniem binarnym sprawdzić, czy liczba się znajduje w tablicy z liczbami pierwszymi.

Po trzecie, jeżeli sędzia na spoju puszcza takie rozwiązanie, to jest to sytuacja dla mnie dziwna.
komentarz 30 kwietnia 2018 przez Kamil Paradowski Użytkownik (620 p.)
Wykorzystałem sztuczkę związaną z metodą naiwną. https://pl.m.wikipedia.org/wiki/Test_pierwszości

Mianowicie ostatni punkt w podpunkcie "Metody naiwne". Stąd moja tablica liczb pierwszych, która nie przekracza wartości pierwiastka z 10000.

Podobne pytania

0 głosów
0 odpowiedzi 364 wizyt
0 głosów
0 odpowiedzi 236 wizyt
pytanie zadane 17 czerwca 2018 w SPOJ przez Kamil Paradowski Użytkownik (620 p.)
0 głosów
0 odpowiedzi 84 wizyt
pytanie zadane 1 sierpnia w C i C++ przez Jakub005 Nowicjusz (180 p.)

91,824 zapytań

140,490 odpowiedzi

316,950 komentarzy

61,159 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...