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.