アカウント名:
パスワード:
d bitの除算はNewton-Raphsonで近似計算すればケチらなくってもlog d回の乗算(と加減算)で終りますよ。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」
エラトステネスの篩 (スコア:0)
(defun prime-p (n)
(let ((v (make-array (1+ n) :initial-element t)))
(setf (aref v 0) nil)
(setf (aref v 1) nil)
(dotimes (i (1+ n))
(when (aref v i)
(do ((j (+ i i) (+ i j)))
((> i n))
(setf (aref v j) nil))))
(aref v n)))
;; C で
Re:エラトステネスの篩 (スコア:3, 参考になる)
Re:エラトステネスの篩 (スコア:0)
# 掛け算は FFTで速くできる、とかきいたが。
Re:エラトステネスの篩 (スコア:3, 参考になる)
商と余りを求める除算の計算量はよく知りません。素朴には O(d^2) 時間でやっているように思いますが。
鵜呑みにしてみる?
Re:エラトステネスの篩 (スコア:2, 参考になる)
ちなみに各近似ステップで
Re:エラトステネスの篩 (スコア:1)
鵜呑みにしてみる?