Skip to content

Latest commit

 

History

History
95 lines (82 loc) · 2.29 KB

README.md

File metadata and controls

95 lines (82 loc) · 2.29 KB
Raw

primecount

Prime counting of sublinear complexity in Common Lisp.

Time  Complexity: O(x3/4)  
Space Complexity: O(x1/2)

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

x Prime Count SBCL CCL CLISP
109 50847534 0.06s 0.19s 1.64s
1010 455052511 0.29s 0.97s 8.47s
1011 4118054813 1.47s 5.03s 43.26s
1012 37607912018 7.61s 25.88s 222.36s

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.