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.
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.
;; 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)
cd ~/my/quicklisp/local-projects/ git clone https://github.com/AaronChen0/primecount.git
The origin idea came from Lucy_Hedgehog from projecteuler.
It uses an optimized sieving method as shown in sympy.
Implement more efficient algorithms in pure Common Lisp.
A good reference is https://github.com/kimwalisch/primecount.