kozima #4865(2007/12/18 05:02 GMT) [ Common Lisp ] Rating2/2=1.00
(meertens n) で n 桁以下のものを探します。n=10 のとき、CLISP で1.6秒、SBCL で 0.5秒ほど(Celeron 2.66GHz)。
8～13 で試してみたところ桁数を1増やすごとにほぼ3倍になっているようなので、20桁の場合 SBCL なら単純計算で8時間ぐらいでしょうか。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
(defconstant *primes* '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)) (defun primes (n) (loop repeat n for p in *primes* collect p)) (defun basis (n) (loop repeat n for x = (expt 10 (1- n)) then (/ x 10) collect x)) (defun f (primes basis bound prod sum zero-ok) (if primes (loop for i from (if zero-ok 0 1) to 9 as dp = (expt (car primes) i) and ds = (* i (car basis)) while (<= dp bound) nconc (f (cdr primes) (cdr basis) (floor bound dp) (* prod dp) (+ sum ds) t)) (if (= prod sum) (list sum) nil))) (defun meertens (n) (loop for i from 1 to n nconc (f (primes i) (basis i) (expt 10 i) 1 0 nil)))
Rating2/2=1.00-0+
2 replies [ reply ]
kozima
#4865()
[
Common Lisp
]
Rating2/2=1.00
(meertens n) で n 桁以下のものを探します。n=10 のとき、CLISP で1.6秒、SBCL で 0.5秒ほど(Celeron 2.66GHz)。
8～13 で試してみたところ桁数を1増やすごとにほぼ3倍になっているようなので、20桁の場合 SBCL なら単純計算で8時間ぐらいでしょうか。
(defconstant *primes* '(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)) (defun primes (n) (loop repeat n for p in *primes* collect p)) (defun basis (n) (loop repeat n for x = (expt 10 (1- n)) then (/ x 10) collect x)) (defun f (primes basis bound prod sum zero-ok) (if primes (loop for i from (if zero-ok 0 1) to 9 as dp = (expt (car primes) i) and ds = (* i (car basis)) while (<= dp bound) nconc (f (cdr primes) (cdr basis) (floor bound dp) (* prod dp) (+ sum ds) t)) (if (= prod sum) (list sum) nil))) (defun meertens (n) (loop for i from 1 to n nconc (f (primes i) (basis i) (expt 10 i) 1 0 nil)))Rating2/2=1.00-0+
2 replies [ reply ]