The primecount Reference Manual

Table of Contents

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 Fri Jun 26 12:00:11 2020 GMT+0.


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

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.


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

License

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

primecount


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

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)


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

5.2 Internal definitions


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

5.2.1 Types

Type: u128 ()
Package

primecount

Source

primecount.lisp (file)

Type: u64 ()
Package

primecount

Source

primecount.lisp (file)


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

Appendix A Indexes


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

A.1 Concepts

Jump to:   F   L   P  
Index Entry  Section

F
File, Lisp, primecount.asd: The primecount․asd file
File, Lisp, primecount/package.lisp: The primecount/package․lisp file
File, Lisp, primecount/primecount.lisp: The primecount/primecount․lisp file

L
Lisp File, primecount.asd: The primecount․asd file
Lisp File, primecount/package.lisp: The primecount/package․lisp file
Lisp File, primecount/primecount.lisp: The primecount/primecount․lisp file

P
primecount.asd: The primecount․asd file
primecount/package.lisp: The primecount/package․lisp file
primecount/primecount.lisp: The primecount/primecount․lisp file

Jump to:   F   L   P  

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

A.2 Functions

Jump to:   F   P  
Index Entry  Section

F
Function, prime-count: Exported functions
Function, prime-count-mod4: Exported functions
Function, prime-sum: Exported functions

P
prime-count: Exported functions
prime-count-mod4: Exported functions
prime-sum: Exported functions

Jump to:   F   P  

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

A.3 Variables


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

A.4 Data types

Jump to:   P   S   T   U  
Index Entry  Section

P
Package, primecount: The primecount package
primecount: The primecount system
primecount: The primecount package

S
System, primecount: The primecount system

T
Type, u128: Internal types
Type, u64: Internal types

U
u128: Internal types
u64: Internal types

Jump to:   P   S   T   U