# 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 3.0 "Montgomery Scott" on Sun May 15 05:51:33 2022 GMT+0.

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

# 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.

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

## 2 Systems

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

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

### 2.1 primecount

Author

Aaron Chen

MIT

Description

prime counting of sublinear complexity

Source

primecount.asd (file)

Components

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

## 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 files   [Contents][Index]

#### 3.1.1 primecount.asd

Location

primecount.asd

Systems

primecount (system)

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

#### 3.1.2 primecount/package.lisp

Parent

primecount (system)

Location

package.lisp

Packages

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

#### 3.1.3 primecount/primecount.lisp

Dependency

package.lisp (file)

Parent

primecount (system)

Location

primecount.lisp

Exported Definitions
Internal Definitions

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

## 4 Packages

Packages are listed by definition order.

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

### 4.1 primecount

Source

package.lisp (file)

Use List

common-lisp

Exported Definitions
Internal Definitions

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

## 5 Definitions

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

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

### 5.1 Exported definitions

Previous: , Up: Exported definitions   [Contents][Index]

#### 5.1.1 Functions

Function: prime-count N
Package
Source

primecount.lisp (file)

Function: prime-count-mod4 N

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

Package
Source

primecount.lisp (file)

Function: prime-sum N
Package
Source

primecount.lisp (file)

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

### 5.2 Internal definitions

Previous: , Up: Internal definitions   [Contents][Index]

#### 5.2.1 Types

Type: u128 ()
Package
Source

primecount.lisp (file)

Type: u64 ()
Package
Source

primecount.lisp (file)

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

## Appendix A Indexes

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

### A.1 Concepts

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