« 『数学ガール』が面白い | トップページ | Project Euler - Problem 43 : Pandigital 数を作ってしまえ »

2009年4月13日 (月)

Project Euler - Problem 37 : 素数を作ってしまえ

Problem 37 は次のような問題でした。

3797は面白い性質を持っている. まずそれ自身が素数であり, 左から右に桁を 除いたときに全て素数になっている (3797, 797, 97, 7). 同様に右から左に桁を除いたときも全て素数である (3797, 379, 37, 3).

右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ.

注: 2, 3, 5, 7を切り詰め可能な素数とは考えない.

まず初めに考えたのが、とにかく条件に合う素数を 11 個探すという方法。

ただし探索する素数の上限が分からないので、奇数を順番に数え上げていって、その数が素数かどうかを判定してから、切り詰め可能かを調べています。

そのため、結果が出るまでかなり時間がかかります (実際、7.6秒かかりました)。

(define problem-037 (lambda () ;; 左右から切り詰めた時、全ての数が素数になるか? (define check (lambda (p) (let loop ([d 10]) (let ([a (quotient p d)] [b (remainder p d)]) (cond ([zero? a] #t) ([and (prime? a) (prime? b)] (loop (* d 10))) (else #f)))))) (let ([result '()] [count 0]) (let loop ([i 11]) (cond ([= count 11] (printf "~d : ~a~%" (apply + result) (reverse result))) ([and (prime? i) (check i)] (set! result (cons i result)) (set! count (+ count 1)) (loop (+ i 2))) (else (loop (+ i 2)))))))) (problem-037)

このコードでは、条件に合う素数が 11 個しかないことを前提にして問題を解いていますが、そもそも 11 個しかないことはどうやって確認されたのでしょうか?

そう考えると、他にもアプローチの仕方があるはずです。


ということで、考え方を逆転させて、条件に合う素数を作ってみることにします。どういうことかというと、一桁の素数の右か左に数字を一つずつ付けていって素数になるものを探してみます。

では、右と左、どちらに付けていくほうがいいのでしょうか?


まず、左に付けていく場合。

実は一桁目が素数の場合、左に付ける数が 1 〜 9 のいずれでも素数になる可能性があります。


次に、右に付けていく場合。

二桁以上の数では、一桁目が偶数や 5 の場合素数ではなくなるので、右に付けられる数は 1, 3, 7, 9 に限定されます。

これだけ限定されれば、どんどん右に数を付け足していっても、いつかは素数が作れなくなるはずです

そこで、素数が作れなくなるまで右に数を付け足していって、できた素数が左詰め可能かをチェックしていきます。

(define problem-037 (lambda () ;; 引数の下に数字を一つ加えて素数を作る。 ;; 右から切り詰める場合の逆の動作。 (define make-new-prime (lambda (p) (filter prime? (map (lambda (x) (+ (* p 10) x)) '(1 3 7 9))))) ;; 引数を左から切り詰める場合の逆の動作でチェック。 (define check (lambda (n) (let loop ([d 10]) (let ([m (remainder n d)]) (cond ([= m n] #t) ([prime? m] (loop (* d 10))) (else #f)))))) (let loop ([lst '(2 3 5 7)] [ans '()]) (if [null? lst] (let ([result (filter check ans)]) (printf "~d : ~a~%" (apply + result) (reverse result))) (let ([new-lst (apply append (map make-new-prime lst))]) (loop new-lst (append new-lst ans))))))) (problem-037)

このコードの場合、探索範囲がかなり限定されるので、0.04 秒しかかかりませんでした。

« 『数学ガール』が面白い | トップページ | Project Euler - Problem 43 : Pandigital 数を作ってしまえ »

Project Euler」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/44656909

この記事へのトラックバック一覧です: Project Euler - Problem 37 : 素数を作ってしまえ:

« 『数学ガール』が面白い | トップページ | Project Euler - Problem 43 : Pandigital 数を作ってしまえ »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ