O(1) runtime prime checking

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3839
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3612
7	Geothermal	3569
8	ecnerwala	3494
9	Um_nik	3396
10	gamegame	3386

№	Пользователь	Вклад
1	Um_nik	164
2	-is-this-fft-	160
2	maomao90	160
4	atcoder_official	158
4	cry	158
4	awoo	158
7	adamant	155
8	nor	154
9	TheScrasse	153
10	Dominater069	152

Hello fellow people of Codeforces

I hope everyone doing well in these uncertain and unprecedented times. I wanted to share this cool C++20 trick that I learned recently.

Check out this cool implementation of is_prime(n) to test if n integer is prime in O(1) runtime (without any runtime precomputation!)

bool is_prime(int n);

#include <iostream>
#include <cstdlib>
#include <ctime>

const int MAXN = 100000;

template<int N>
struct Sieve {
    bool is_prime[N];
    constexpr Sieve() : is_prime() {
        for (int i = 2; i < N; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i < N; i++) if (is_prime[i]) {
            for (int j = 2 * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
};

template<Sieve<MAXN> s>
struct SieveWrapper {
    static bool get(int n) {
        return s.is_prime[n];
    }
};

bool is_prime(int n) {
    return SieveWrapper<Sieve<MAXN>{}>::get(n);
}

/*
bool slow_is_prime(int n) {
    return (Sieve<MAXN>{}).is_prime_[n];
}
*/
    
int main() {
    auto t1 = time(NULL);
    
    // compute answer for 1000 random integers
    int ans = 0;
    for (int i = 0; i < 1000; i++) {
        ans += is_prime(rand() % MAXN);
    }

    auto t = time(NULL) - t1;

    std::cout << "Answer: " << t << ". Elapsed time: " << t << "s" << std::endl;
}

This code computes primes up to MAXN during compilation and stores them in a table right in the compiled binary. On a runtime is_prime(n) call, it queries the compiled table to find the result. Check this compiled assembly to find the sieve mask baked in the binary: https://godbolt.org/z/G6o84x.

This trick is achieved by passing the constructed Sieve as a template argument, which is always evaluated on compile-time. If you compile this code using older C++ standard, you will get the error:

error: a non-type template parameter cannot have type 'Sieve<MAXN>'

However, since C++20, non-type template parameter can have any LiteralType (note). In short, it is possible to compile-time compute an instance of any class with a constexpr constructor.

Here is a time test of compile-time vs run-time sieve computation:

main.cpp

#include <iostream>
#include <vector>
#include <chrono>
#include <cstdlib>

using namespace std;

const int MAXN = 100000;

template<int N>
struct Sieve {
    bool is_prime[N];
    constexpr Sieve() : is_prime() {
        for (int i = 2; i < N; i++) {
            is_prime[i] = true;
        }
        for (int i = 2; i < N; i++) if (is_prime[i]) {
            for (int j = 2 * i; j < N; j += i) {
                is_prime[j] = false;
            }
        }
    }
};

template<Sieve<MAXN> s>
struct SieveWrapper {
    static bool get(int n) {
        return s.is_prime[n];
    }
};

bool fast_is_prime(int n) {
    return SieveWrapper<Sieve<MAXN>{}>::get(n);
}


bool slow_is_prime(int n) {
    return (Sieve<MAXN>{}).is_prime[n];
}


const int reps = 1000;
int main() {
    vector<int> numbers(reps);
    for (int i = 0; i < reps; i++) {
        numbers[i] = rand() % MAXN;
    }

    int ans = 0;
    auto t1 = chrono::high_resolution_clock::now();
    for (auto &n : numbers) {
        ans += slow_is_prime(n);
    }
    auto t2 = chrono::high_resolution_clock::now();
    cout << "Runtime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;

    ans = 0;
    t1 = chrono::high_resolution_clock::now();
    for (auto &n : numbers) {
        ans += fast_is_prime(n);
    }
    t2 = chrono::high_resolution_clock::now();
    cout << "Compiletime ans: " << ans << ". Elapsed (ms): " << chrono::duration_cast<chrono::milliseconds>(t2 - t1).count() << endl;
}

Compiled with GCC 9.3.0 using the command g++ -std=c++2a main.cpp. This is the execution output on my laptop:

Runtime ans: 90. Elapsed (ms): 1008
Compiletime ans: 90. Elapsed (ms): 0

Of course no one re-computes sieve 1000 times, this is done here for the sole purpose of showing that the algorithm is not computing sieve in run time 1000 times.

While such tricks won't help you cheat pass Codeforces problems, they might will help your submission stand out for fastest runtimes. Hope you found this interesting!

Rev.	Кто	Когда	Δ	Комментарий
en3	tweety	2020-07-10 08:23:30	31	Tiny change: ' assembly on the left side of the screen to find t' -> ' assembly to find t'
en2	tweety	2020-07-10 08:15:59	40	Tiny change: '1) runtime\n\n<spoil' -> '1) runtime (without any runtime precomputation!)\n\n<spoil'
en1	tweety	2020-07-10 08:15:17	4713	Initial revision (published)

История