« Project Euler - Problem 45 | トップページ | "math_tool.rb" by Ruby 1.9.1 »

2009年5月22日 (金)

Project Euler - Problem 35

* 今回の内容は、以前投稿した内容を一部修正して、Ruby のコードを加えたものです。


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

197は巡回素数と呼ばれる. 桁を回転させたときに得られる数 197, 971, 719 が全て素数だからである.

100未満には巡回素数が13個ある: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, および 97 である. 100万未満の巡回素数は何個か?

100 万未満の素数の全てで巡回素数かどうかを調べると、

(length (prime-list 1000000)) ; => 78498

78498 個もの素数を調べる必要があります。


そこで、もう少し考えてみましょう。

2 桁以上の素数で、偶数または 5 を含むものは、巡回しているうちに偶数または 5 が一の位になった時点で、素数でなくなります。ならば偶数や 5 を含む素数は最初から除外しておけば、調べる数が減るはずです。

ということで、私は以下のようなコードを書いてみました。いかがでしょうか?

(define problem-035 (lambda (n-max) ;; 偶数または 5 を含んでいるか? (define include_even_or_5? (lambda (lst) (if [null? (cdr lst)] #f (exists (lambda (x) (memv x lst)) '(0 2 4 5 6 8))))) ;; 循環素数となるリストか? (define circular? (lambda (lst) (let* ([len (length lst)] [lst-a (append lst lst)]) (let loop ([lst-a (cdr lst-a)]) (cond ([= (length lst-a) len] #t) ([prime? (list->integer (list-head lst-a len))] (loop (cdr lst-a))) (else #f)))))) (let* ([lst-a (map integer->list (prime-list n-max))] [lst-b (remp include_even_or_5? lst-a)] [lst-c (filter circular? lst-b)]) (printf "~d~%~a~%" (length lst-c) (map list->integer lst-c))))) (problem-035 1000000)


ちなみに、Ruby だとこんなかんじでしょうか?

# -*- coding: utf-8 -*- include Math class Integer # # 素数の判定 # def prime? return false if (self <= 1) return true if (self == 2) return false if (self.even?) 3.step(sqrt(self).to_i, 2) do |i| return false if (self.modulo(i) == 0) end return true end # # 整数を配列に変換する。 # ex : 123.to_a => [1, 2, 3] # ex : 123.to_a(2) => [1, 1, 1, 1, 0, 1, 1] # def to_a(radix = 10) n = self a = Array.new while (n >= radix) do a.unshift(n.modulo(radix)) n = n / radix end a.unshift(n) end end # # n 以下の素数を要素とする配列を返す。 # ex : prime_list(20) => [2, 3, 5, 7, 11, 13, 17, 19] # def prime_list(n) return([]) if (n <= 1) size = n / 2 - 1 max = sqrt(n).to_i a = Array.new(size) size.times do |i| a[i] = 2 * i + 3 end a.unshift(nil) max.times do |i| j = a[i] next unless j (2 * i * (i + 1)).step(size, j) do |k| a[k] = nil end end return a.unshift(2).compact end class Array # # 配列を整数に変換する。 # ex : [1, 2, 3].to_i => 123 # ex : [1, 1, 1, 1, 0, 1, 1].to_i(2) => 123 # def to_i(radix = 10) sum = 0 self.each do |i| sum = sum * radix + i if (i < radix) end return sum end # # 偶数または 5 を含むか? # def check_even_and_5 return false if self.length == 1 if [0, 2, 4, 5, 6, 8].any? {|x| self.include?(x)} then return true else return false end end # # 循環素数になるリストか? # def circular? a_size = self.size a = self * 2 a_size.times do |i| next if i.zero? return false if not a[i, a_size].to_i.prime? end return true end end p_list = prime_list(100_0000).map {|x| x.to_a} p_list = p_list.delete_if {|x| x.check_even_and_5} p_list = p_list.select {|x| x.circular?} print("#{p_list.size}\n") p p_list.map {|x| x.to_i}

« Project Euler - Problem 45 | トップページ | "math_tool.rb" by Ruby 1.9.1 »

Project Euler」カテゴリの記事

Ruby」カテゴリの記事

Scheme」カテゴリの記事

コメント

コメントを書く

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

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

トラックバック

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

この記事へのトラックバック一覧です: Project Euler - Problem 35:

« Project Euler - Problem 45 | トップページ | "math_tool.rb" by Ruby 1.9.1 »

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            
フォト

最近のトラックバック

無料ブログはココログ