Liczby Pierwsze - SPOJ Jak uzyskać czas 0.00?

Question

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 :)

Answer 1

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.

Answer 2

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.

Comments

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

Answer 3

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.

Comments

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.

---

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.

---

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.