Nice :) I wonder if you can do this in earlier versions of C++ by having just the is_prime array be compile-time computed (instead of the Sieve instance)

It might be worth it to try space-saving tricks like bit-packing and wheel sieve to increase max_N, the runtime penalty should be small, bit-packing should increase max_n by 8x, the simplest wheel sieve (omit all even numbers) should increase it further by 2x.

I think this can be done with C++14. Also you don't need a Wrapper class:

bool fast_is_prime(int n) {
    static constexpr Sieve<MAXN> s;
    return s.is_prime[n];
}

Runtime ans: 100. Elapsed (ms): 583
Compiletime ans: 100. Elapsed (ms): 0

See C++14 on ideone

Do you have more tricks up your sleeve? If so please make a series or something like that. I found this really helpful.

Amazing, provide a new idea to cost compile-time instead of exec-time ! It may useful for particluar questions since CP only care about exec-time.

But: ‘constexpr’ loop iteration count has limit of 262144 (use ‘-fconstexpr-loop-limit=’ to increase the limit), and we can't use -fconstexpr-loop-limit= parameter in CP, sadly this ideal may can't put prime sieve in practice even ...._.._ provide C++14(So C++17 works) version of your idea.

https://www.cs.utexas.edu/users/misra/scannedPdf.dir/linearSieve.pdf the original paper

#include <chrono>
#include <cstdlib>
#include <iostream>
#include <vector>
 
using namespace std;

const int MAXN = 262144;
 
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;
                }
            }
    }
};

struct sieve {
    bool ip[1000000];
    bool done[1000000] = {0};
    sieve () {
        ip[0] = ip[1] = false;
        ip[2] = true;
        done[0] = done[1] = true;
        for (int i = 2; i <= 1e6; i++) {
            if (done[i]) continue;
            ip[i] = true;
            done[i] = true;
            for (int j = i * 2; j <= 1e6; j += i) {
                ip[j] = false;
                done[j] = true;
            }
        }
    }
};
 
bool fast_is_prime(int n) {
    static constexpr Sieve<MAXN> s;
    return s.is_prime[n];
}
 
bool slow_is_prime(int n) {
    return (Sieve<MAXN>{}).is_prime[n];
}
 
const int reps = 10000000;
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();
    sieve st;
    for (auto &n : numbers) {
        ans += st.ip[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;
}

in this code i added another simple sieve struct, and compared both

a@a:~/Desktop/Cp$ ./a.out <- sample count 1e6
Runtime ans: 86783. Elapsed (ms): 29
Compiletime ans: 86783. Elapsed (ms): 13
a@a:~/Desktop/Cp$ g++ test.cpp <- sample count 1e7
a@a:~/Desktop/Cp$ ./a.out
Runtime ans: 877166. Elapsed (ms): 124
Compiletime ans: 877166. Elapsed (ms): 134

i don't think this is a satisfactory change ?

Hi! Can someone explain what is meant by "While such tricks won't help you cheat pass Codeforces problems". How come this trick wouldn't help with CF submissions? Will the time spent compiling be added onto runtime or something?

1. This trick works in C++14, and needs neither a wrapper class nor a wrapper function:

template<std::size_t N>
struct Sieve 
{
	private:
		bool is_prime[N];
	public:
		constexpr Sieve() : is_prime{0}
		{
			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;
					}
				}
			}
		}
		inline constexpr bool operator[](std::size_t index) const
		{
			return is_prime[index];
		}
};


int main()
{
	//Sieve
	constexpr int MaxN = 1e5;
	Sieve<MaxN> isPrime;

	assert(isPrime[5]);
	//More code here...
}

You can check the assembly here. Starting from line 106, many mov statements are copying bytes to the addresses that should hold prime numbers. Apparently, the constexpr constructor has forced all instances of Sieve to be built in compile time, and the overloading of operator[] allows simple array syntax on the Sieve.

2. This trick may be useful for MaxN <= 1e5, but not higher.

Although compile-time evaluation may theoretically make it possible to compute the Sieve for up to MaxN = 1e9, constexpr evaluation does have a large cost during compile time and also on the binary size. Therefore, setting MaxN to 1e7 or greater may cause the compiler to either crash or report an error, even if -fconstexpr-loop-limit= is set to a large number, while runtime building of a sieve of 1e7 elements is always possible.