Zadanko 'liczby pierwsze' ze pl.spoj.com

Od dawna mam zrobione to zadanko ale o czasie aż 0.01 .
czy postarać się włożyć ciało funkcji do maih?

O ile dobrze pamiętam, w tym zadaniu da się stworzyć tablicę bool i "wpakować" do niej co jest liczbą pierwszą a co nie. Żadnych funkcji nie trzeba

Tak, chociaz, ciekawe czy Miller-Rabin by dal rade.

Co do zasady, wspóczesne kompilatory są na tyle sprytne, że się zorientują, czy inline’owanie funkcji w prostych programach ma sens, czy nie, bez ręcznej interwencji.

Spróbować można, ale początkujący mają potężną tendencję do przeceniania wpływu takich mikrooptymalizacji…

Możesz też zamiast przenosić kod z funkcji do funkcji wywołującej po prostu nadać tej funkcji kwalifikator inline co powinno spowodować to samo (chociaż zdarza się że niektóre kompilatory ignorują ten kwalifikator) mimo że logicznie w kodzie źródłowym funkcja pozostanie odrębną funkcją.

Ja jeszcze dodam do wypowiedzi @Althorion że takie mikrooptymalizacje (w ogólności) mają tyle samo sensu co dyskusja czy i++ vs ++i. Oczywiście przy 1 000 000 000 000 wywołań 1 linijkowej funkcji może mieć znaczenie do ogólnej wydajności.

W tym przypadku pewnie problem jest gdzieś indziej. Spoj jak to spoj, tutaj czasami nawet do zaliczenia zadania wymagane będzie odprawianie magii na IO celem zmieszczenia się w limitach. Swoją drogą 0.01 to nie jest zły wynik. Algorytm zapewne masz optymalny. Musisz szukać w Fast I/O. Jest tam parę tematów na forum.

Przy tak niskim czasie, pomóc by pewnie mogło nawet i przechowanie wyników w stringu (nowa linia jako "rozdzielacz), i wypisanie ich naraz po zakończeniu wszystkich obliczeń

sig napisał(a):

O ile dobrze pamiętam, w tym zadaniu da się stworzyć tablicę bool i "wpakować" do niej co jest liczbą pierwszą a co nie. Żadnych funkcji nie trzeba

Niedawno się zastanawiałem patrząc na zadania na spoj jakie tam jest podejście do używania lookup table. Czy temat prowokował jakieś debaty.

#include <iostream>
#include <array>
#include <exception>

template<size_t N>
class EratostenesSive
{
public:
    constexpr EratostenesSive()
    {
        oddPrimes[0] = false;
        for(size_t i = 1; i < (N + 1) / 2; ++i) oddPrimes[i] = true;
        
        for (size_t p = 3; p * p <= N; p += 2) {
            if (oddPrimes[p/2]) {
                for (size_t i = p * p; i <= N; i += 2 * p) {
                    oddPrimes[i/2] = false;
                }
            }
        }
    }
    
    constexpr bool isPrime(size_t x) const
    {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x > max()) throw std::invalid_argument("Sive limit reached");
        return x%2 != 0 && oddPrimes[x/2];
    }
    
    constexpr size_t max() const {
        return N | 1;
    }
    
private:
    bool oddPrimes[(N + 1) / 2] = {};
};

constexpr auto primes = EratostenesSive<100000>{};

int main()
{
	static constexpr const char* const boolDesc[] {
	    "NIE\n",
	    "TAK\n",
	};
    size_t x, n;
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    while (n-- && std::cin >> x) {
        std::cout << boolDesc[primes.isPrime(x)];
    }
    return 0;
}

Takie coś, operate o constexpr kompiluje się jako C++14 clang 8.0 i gcc 8.3.
Ergo ładna look up table obliczana w trakcie kompilacji.
Niestarty uzyskuje zwykle czas 0.02 a jedno uruchomianie dało 0.01.
Żeby uzyskać 0.00 stawiam na jakiś jakieś optymalizacje operacji IO, względnie szczęście podczas pomiaru czasu (na SPOJ jest spoko LeetCode pot tym względem to tragedia).

https://godbolt.org/z/WzWsTxacq