The primecount Reference Manual

Next: , Previous: , Up: (dir)   [Contents][Index]

The primecount Reference Manual

This is the primecount Reference Manual, generated automatically by Declt version 4.0 beta 2 "William Riker" on Thu Sep 15 05:54:39 2022 GMT+0.

Table of Contents


1 Introduction

primecount

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.

Benchmarks

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.

Usage Examples

;; 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)

Installation

cd ~/my/quicklisp/local-projects/
git clone https://github.com/AaronChen0/primecount.git
(ql:quickload "primecount")

Algorithm

The origin idea came from Lucy_Hedgehog from projecteuler.
It uses an optimized sieving method as shown in sympy.

Todo

Implement more efficient algorithms in pure Common Lisp.
A good reference is https://github.com/kimwalisch/primecount.


2 Systems

The main system appears first, followed by any subsystem dependency.


Previous: , Up: Systems   [Contents][Index]

2.1 primecount

prime counting of sublinear complexity

Author

Aaron Chen

License

MIT

Source

primecount.asd.

Child Components

3 Files

Files are sorted by type and then listed depth-first from the systems components trees.


Previous: , Up: Files   [Contents][Index]

3.1 Lisp


Next: , Previous: , Up: Lisp   [Contents][Index]

3.1.1 primecount/primecount.asd

Source

primecount.asd.

Parent Component

primecount (system).

ASDF Systems

primecount.


3.1.2 primecount/package.lisp

Source

primecount.asd.

Parent Component

primecount (system).

Packages

primecount.


3.1.3 primecount/primecount.lisp

Dependency

package.lisp (file).

Source

primecount.asd.

Parent Component

primecount (system).

Public Interface
Internals

4 Packages

Packages are listed by definition order.


Previous: , Up: Packages   [Contents][Index]

4.1 primecount

Source

package.lisp.

Use List

common-lisp.

Public Interface
Internals

5 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.


Next: , Previous: , Up: Definitions   [Contents][Index]

5.1 Public Interface


5.1.1 Ordinary functions

Function: prime-count (n)
Package

primecount.

Source

primecount.lisp.

Function: prime-count-mod4 (n)

Count primes of the forms 4m+1 and 4m+3 no larger than n.

Package

primecount.

Source

primecount.lisp.

Function: prime-sum (n)
Package

primecount.

Source

primecount.lisp.


5.2 Internals


Previous: , Up: Internals   [Contents][Index]

5.2.1 Types

Type: u128 ()
Package

primecount.

Source

primecount.lisp.

Type: u64 ()
Package

primecount.

Source

primecount.lisp.


Appendix A Indexes


Next: , Previous: , Up: Indexes   [Contents][Index]

A.1 Concepts


Next: , Previous: , Up: Indexes   [Contents][Index]

A.3 Variables