問題1.22

(eval-when (:compile-toplevel :load-toplevel :execute)
  (ql:quickload "cffi"))

(cffi:defcvar "errno" :int)

(cffi:defcfun "strerror" :string
  "Map the error number to a locale-dependent error message string."
  (errnum :int))

(cffi:define-foreign-library librt
  (t (:default "librt")))

(cffi:use-foreign-library librt)

(cffi:defctype clockid-t :int)
(cffi:defctype time-t :long)

(cffi:defcstruct timespec
  (tv_sec time-t)
  (tv_nsec :long))

(cffi:defcfun (%clock-gettime "clock_gettime") :int
  (clock-id clockid-t)
  (tp (:pointer timespec)))

(defconstant +clock-realtime+ 0)
(defconstant +clock-monotonic+ 1)
(defconstant +clock-process-cputime+ 2)
(defconstant +clock-thread-cputime+ 3)

(defun clock-gettime (clock-id)
  "Return the current value for the specified clock."
  (let ((id (ccase clock-id
              ((:realtime) +clock-realtime+)
              ((:monotonic) +clock-monotonic+)
              ((:process-cputime) +clock-thread-cputime+)
              ((:thread-cputime) +clock-thread-cputime+))))
    (cffi:with-foreign-object (tp 'timespec)
      (unless (zerop (%clock-gettime id tp))
        (error "Foreign function clock-gettime faild: ~a" (strerror *errno*)))
      (values (cffi:foreign-slot-value tp 'timespec 'tv_sec)
              (cffi:foreign-slot-value tp 'timespec 'tv_nsec)))))

(defmacro runtime ()
  `(multiple-value-bind (sec nsec)
       (clock-gettime :process-cputime)
     (+ (* sec (expt 10 9)) nsec)))

(defun dividesp (a b)
  (zerop (mod b a)))

(defun find-divisor (n test-divisor)
  (cond ((> (expt test-divisor 2) n) n)
        ((dividesp test-divisor n) test-divisor)
        (t (find-divisor n (1+ test-divisor)))))

(defun smallest-divisor (n)
  (find-divisor n 2))

(defun primep (n)
  (= n (smallest-divisor n)))

(defun report-prime (elapsed-time)
  (princ " *** ")
  (princ elapsed-time))

(defun start-prime-test (n start-time)
  (when (primep n)
    (report-prime (- (runtime) start-time))))

(defun timed-prime-test (n)
  (terpri)
  (princ n)
  (start-prime-test n (runtime)))

(defun search-for-primes (start end)
  (when (oddp start)
    (timed-prime-test start))
  (when (< start end)
    (search-for-primes (1+ start) end)))

runtimeがないので、clock_gettimeを使って定義する。精度はナノ秒。また、定義が自明なため、奇数の判別には組み込みのoddpを使っている。

> (search-for-primes 1000 1050)

1001
1003
1005
1007
1009 *** 9114
1011
1013 *** 8887
1015
1017
1019 *** 9054
1021 *** 9078
1023
1025
1027
1029
1031 *** 9275
1033 *** 9431
1035
1037
1039 *** 9162
1041
1043
1045
1047
1049 *** 9066
NIL
> (search-for-primes 10000 10050)

10001
10003
10005
10007 *** 23444
10009 *** 23803
10011
10013
10015
10017
10019
10021
10023
10025
10027
10029
10031
10033
10035
10037 *** 23983
10039 *** 23486
10041
10043
10045
10047
10049
NIL
> (search-for-primes 100000 100050)

100001
100003 *** 73907
100005
100007
100009
100011
100013
100015
100017
100019 *** 73650
100021
100023
100025
100027
100029
100031
100033
100035
100037
100039
100041
100043 *** 73279
100045
100047
100049 *** 73584
NIL
> (search-for-primes 1000000 1000050)

1000001
1000003 *** 217447
1000005
1000007
1000009
1000011
1000013
1000015
1000017
1000019
1000021
1000023
1000025
1000027
1000029
1000031
1000033 *** 216698
1000035
1000037 *** 216829
1000039 *** 227579
1000041
1000043
1000045
1000047
1000049
NIL

おおむねそれらしい値になっている。純粋な処理時間以外にも、手続きを呼び出すオーバーヘッドなども含まれるので、多少の誤差は許容範囲内と思われる。