GitHub - SheafificationOfG/QueenJewels: On a hunt for the Jewels of the Queen of Mathematics... in LLVM IR · GitHub
/" data-turbo-transient="true" />
Skip to content
Search or jump to...
Search code, repositories, users, issues, pull requests...
-->
Search
Clear
Search syntax tips
Provide feedback
--><br>We read every piece of feedback, and take your input very seriously.
Include my email address so I can be contacted
Cancel
Submit feedback
Saved searches
Use saved searches to filter your results more quickly
-->
Name
Query
To see all available qualifiers, see our documentation.
Cancel
Create saved search
Sign in
/;ref_cta:Sign up;ref_loc:header logged out"}"<br>Sign up
Appearance settings
Resetting focus
You signed in with another tab or window. Reload to refresh your session.<br>You signed out in another tab or window. Reload to refresh your session.<br>You switched accounts on another tab or window. Reload to refresh your session.
Dismiss alert
{{ message }}
SheafificationOfG
QueenJewels
Public
Notifications<br>You must be signed in to change notification settings
Fork
Star<br>27
main
BranchesTags
Go to file
CodeOpen more actions menu
Folders and files<br>NameNameLast commit message<br>Last commit date<br>Latest commit
History<br>2 Commits<br>2 Commits
algo
algo
docs
docs
output
output
scripts
scripts
.gitignore
.gitignore
Makefile
Makefile
README.md
README.md
amd64_rt.ll
amd64_rt.ll
amd64_sys.ll
amd64_sys.ll
main.ll
main.ll
View all files
Repository files navigation
Searching for the Jewels of the Queen
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.
One second to find the BILLIONth PRIME
Note<br>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<br>./scripts/bench.py ./output/bin/${algo}.out -o benchmark.data
Tip<br>Consult the Software Requirements to obtain the necessary binaries, or configure which binaries to use.
Algorithms
Strategy<br>Algorithm<br>Target (output/bin/)<br>Runtime
Iterate
*-iterate.out
Naïve<br>naive-iterate.out<br>$O(n^2)$
Square-root<br>sqrt-iterate.out<br>$O(n^{3/2})$
Miller-Rabin<br>miller-rabin-iterate.out<br>$O(n\log n)$
Sieve
sieve-*.out
Sieve of Eratosthenes<br>sieve-erat-sqrt.out<br>$O(n\log n\log\log n)$
Segmented Sieve of Eratosthenes<br>sieve-erat-segm.out<br>$O(n\log n\log\log n)$
Sieve of Pritchard<br>sieve-pritchard.out<br>$O(\frac{n\log n}{\log\log n})$
Wheel-factorised Segmented Sieve of Eratosthenes<br>sieve-erat-wheel.out<br>$O(n\log n\log\log n)$
Lagrange's formula<br>sieve-lagrange.out<br>🤷1
Footnotes
🤷 ↩
About
On a hunt for the Jewels of the Queen of Mathematics... in LLVM IR
Topics
prime-numbers
llvm-ir
Resources
Readme
Uh oh!
There was an error while loading. Please reload this page.
Activity
Custom properties
Stars
27<br>stars
Watchers
watching
Forks
forks
Report repository
Contributors
Uh oh!
There was an error while loading. Please reload this page.
Languages
LLVM<br>85.6%
Python<br>10.1%
Makefile<br>4.3%
You can’t perform that action at this time.