GitHub - SheafificationOfG/QueenJewels: On a hunt for the Jewels of the Queen of Mathematics... in LLVM IR

The goal is to efficiently compute the $n$-th prime $p_n$, so as to maximise $n$ for which we can compute $p_n$ within one second.

Note

We use the (awful, self-inflicted) convention that $p_0 := 2$.

Usage

All of the algorithms can be compiled with

make output/bin/${algo}.out

for an appropriate value of ${algo} (see below).

Once you have successfully built a binary, the usage is quite straightforward: to compute $p_n$, run

./output/bin/${algo}.out $n

To benchmark an algorithm, use the provided script:

# to generate benchmark data
./scripts/bench.py ./output/bin/${algo}.out -o benchmark.data

Tip

Consult the Software Requirements to obtain the necessary binaries, or configure which binaries to use.

Strategy	Algorithm	Target (`output/bin/`)	Runtime
Iterate		`*-iterate.out`
	Naïve	`naive-iterate.out`	$O(n^2)$
	Square-root	`sqrt-iterate.out`	$O(n^{3/2})$
	Miller-Rabin	`miller-rabin-iterate.out`	$O(n\log n)$
Sieve		`sieve-*.out`
	Sieve of Eratosthenes	`sieve-erat-sqrt.out`	$O(n\log n\log\log n)$
	Segmented Sieve of Eratosthenes	`sieve-erat-segm.out`	$O(n\log n\log\log n)$
	Sieve of Pritchard	`sieve-pritchard.out`	$O(\frac{n\log n}{\log\log n})$
	Wheel-factorised Segmented Sieve of Eratosthenes	`sieve-erat-wheel.out`	$O(n\log n\log\log n)$
	Legendre's formula	`sieve-legendre.out`	🤷¹