Next: Introduction, Previous: (dir), Up: (dir) [Contents][Index]
This is the primecount Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Sun May 15 05:51:33 2022 GMT+0.
• Introduction | What primecount is all about | |
• Systems | The systems documentation | |
• Files | The files documentation | |
• Packages | The packages documentation | |
• Definitions | The symbols documentation | |
• Indexes | Concepts, functions, variables and data types |
Prime counting of sublinear complexity in Common Lisp.
Using sbcl, it can count primes under 10^12 under 8s, which outperforms sympy and pari-gp.
Also it can sum primes, count primes of the forms 4m+1 and 4m+3.
The benchmarks were made on my 1.9 GHz old laptop.
It can be seen that the gaps between different lisp systems
are quite large.
;; count primes <= 10^11
(primecount:prime-count (expt 10 11))
;; sum primes <= 10^11
(primecount:prime-sum (expt 10 11))
;; count primes of the forms 4m+1 and 4m+3 <= 10^11
;; (values 4m+1 4m+3)
(primecount:prime-count-mod4 (expt 10 11))
;; test if the results of prime-count match those of
;; prime-count-mod4
(defun test (range times)
(loop repeat times
for i = (+ 2 (random range))
do (multiple-value-bind (n1 n3)
(primecount:prime-count-mod4 i)
(assert (= (primecount:prime-count i)
(+ n1 n3 1))))))
(test 1000000000 10)
cd ~/my/quicklisp/local-projects/
git clone https://github.com/AaronChen0/primecount.git
(ql:quickload "primecount")
The origin idea came from Lucy_Hedgehog from projecteuler.
It uses an optimized sieving method as shown in
sympy.
Implement more efficient algorithms in pure Common Lisp.
A good reference is https://github.com/kimwalisch/primecount.
Next: Files, Previous: Introduction, Up: Top [Contents][Index]
The main system appears first, followed by any subsystem dependency.
• The primecount system |
Aaron Chen
MIT
prime counting of sublinear complexity
primecount.asd (file)
Files are sorted by type and then listed depth-first from the systems components trees.
• Lisp files |
• The primecount.asd file | ||
• The primecount/package.lisp file | ||
• The primecount/primecount.lisp file |
Next: The primecount/package․lisp file, Previous: Lisp files, Up: Lisp files [Contents][Index]
primecount.asd
primecount (system)
Next: The primecount/primecount․lisp file, Previous: The primecount․asd file, Up: Lisp files [Contents][Index]
primecount (system)
package.lisp
Previous: The primecount/package․lisp file, Up: Lisp files [Contents][Index]
package.lisp (file)
primecount (system)
primecount.lisp
Next: Definitions, Previous: Files, Up: Top [Contents][Index]
Packages are listed by definition order.
• The primecount package |
package.lisp (file)
common-lisp
Definitions are sorted by export status, category, package, and then by lexicographic order.
• Exported definitions | ||
• Internal definitions |
Next: Internal definitions, Previous: Definitions, Up: Definitions [Contents][Index]
• Exported functions |
Previous: Exported definitions, Up: Exported definitions [Contents][Index]
primecount.lisp (file)
Count primes of the forms 4m+1 and 4m+3 no larger than n.
primecount.lisp (file)
primecount.lisp (file)
Previous: Exported definitions, Up: Definitions [Contents][Index]
• Internal types |
Previous: Internal definitions, Up: Internal definitions [Contents][Index]
primecount.lisp (file)
primecount.lisp (file)
Previous: Definitions, Up: Top [Contents][Index]
• Concept index | ||
• Function index | ||
• Variable index | ||
• Data type index |
Next: Function index, Previous: Indexes, Up: Indexes [Contents][Index]
Jump to: | F L P |
---|
Jump to: | F L P |
---|
Next: Variable index, Previous: Concept index, Up: Indexes [Contents][Index]
Jump to: | F P |
---|
Jump to: | F P |
---|
Next: Data type index, Previous: Function index, Up: Indexes [Contents][Index]
Previous: Variable index, Up: Indexes [Contents][Index]
Jump to: | P S T U |
---|
Jump to: | P S T U |
---|