The primecount Reference Manual

Table of Contents

The primecount Reference Manual

This is the primecount Reference Manual, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Oct 13 12:12:33 2021 GMT+0.

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.

2.1 primecount

Author

Aaron Chen

License

MIT

Description

prime counting of sublinear complexity

Source

primecount.asd (file)

Components

• package.lisp (file)
• primecount.lisp (file)

3 Files

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

3.1 Lisp

3.1.1 primecount.asd

Location

primecount.asd

Systems

primecount (system)

3.1.2 primecount/package.lisp

Parent

primecount (system)

Location

package.lisp

Packages

primecount

3.1.3 primecount/primecount.lisp

Dependency

package.lisp (file)

Parent

primecount (system)

Location

primecount.lisp

Exported Definitions

• prime-count (function)
• prime-count-mod4 (function)
• prime-sum (function)

Internal Definitions

• u128 (type)
• u64 (type)

4 Packages

Packages are listed by definition order.

4.1 primecount

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions

• prime-count (function)
• prime-count-mod4 (function)
• prime-sum (function)

Internal Definitions

• u128 (type)
• u64 (type)

5 Definitions

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

5.1 Exported definitions

5.1.1 Functions

Function: prime-count N

Package

primecount

Source

primecount.lisp (file)

Function: prime-count-mod4 N

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

Package

primecount

Source

primecount.lisp (file)

Function: prime-sum N

Package

primecount

Source

primecount.lisp (file)

5.2 Internal definitions

5.2.1 Types

Type: u128 ()

Package

primecount

Source

primecount.lisp (file)

Type: u64 ()

Package

primecount

Source

primecount.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions

A.3 Variables

A.4 Data types