getting prime numbers quickly

[TAKAHASHI Naoto <ntakahas@m17n.org>]

n高橋です。もう誰も読んでないかもしれませんが(苦笑)、更に高速化します。

TAKAHASHI Naoto writes:

> ;; n高橋爆速バージョン
> ;; 6n±1法 (2と3は特別扱い)
> ;; xが素数かどうかは、(sqrt x) までの素数で割って調べる
> ;; 関数呼び出しは重いので、+1と-1の両方の場合をインライン展開
> (let* ((primes '(2 3))
>        (tail (last primes))

ここで primes の初期値を '(2 3) としていますが、6n±1法なので2と3で割っ
てみるのは全くの無駄ですね。また最後に primes を値として返すわけでもな
いので、変数名は divisors にでも変えて、初期値は '(5) とした方がいいで
しょう。また '(5) は長さ1のリストなので、次の tail の初期値は
(last divisors) ではなくて単に divisors になります。

また高速化を図るのなら当然バイトコンパイルしますから、わざわざ読みにく
いインライン展開を使わず、defsubst を使うことにします。変数名も、より
整数っぽいものに変えます。結局次のようになります。

;; n高橋爆速バージョン[改]
;; 6n±1法 (2と3は特別扱い)
;; xが素数かどうかは、5以上ルートx以下の素数で割って調べる
;; バイトコンパイルを前提
(defsubst primep (i)
  "Internal use only.  Depends on external variables."
  (setq d divisors
        limit (sqrt i))
  (while (and (<= (car d) limit) (/= 0 (% i (car d))))
    (setq d (cdr d)))
  (when (> (car d) limit)
    (setcdr tail (list i))
    (setq tail (cdr tail))
    (insert (format "%s\n" i))))

(let* ((divisors '(5))
       (tail divisors)
       (n 6)
       d limit)
  (insert "2\n3\n")

  (while (< n 1000)
    (primep (1- n))
    (primep (1+ n))
    (setq n (+ n 6))))

-- 
TAKAHASHI Naoto
ntakahas@...
http://www.m17n.org/ntakahas/