にせいの日記

「自分の好きなものってなんだろう?」という疑問を解決するために、気が向いた時に好きなことを書いてみて、「自分の好きなもの」をあぶり出そうと試みています。

素数大富豪素数問題に挑む -まだ1日目- 場合分けとRuby導入

この記事は、数字のド素人であるにせーが、素数大富豪素数問題に挑む記録です。 

素数大富豪素数問題に挑む -予告- 素数大富豪とは? - にせいの日記

 

素数大富豪素数問題に挑む -1日目- まずはやってみる - にせいの日記

 

〜前回までの進捗〜

  • 素数大富豪素数問題に挑戦しようと決める
  • 地道に数えるのは大変
  • 最大の数は72桁(実際に出せる数は71桁以下)

以上

 

 

<1日目> 2014年12月22日(月)

21:37

「実際にゲームで出せる数」という条件を検討するのが面倒で、あっという間に心折れそうになった1日目。

 

一気にいろいろ考えようとするのは大変なので、場合分けして、できるところから手をつけてようと考えた。

ゲーム的には「何枚で出すか」というのが重要であるので、それに習って「何枚使うか」で場合分けしてみることにした。

 

トランプは、(ジョーカーを除けば)同じ数字は4枚までしかない。

つまり、ジョーカーを含めて6枚までなら好きな数字を好きなように並べることができるけれど、それを越えると話が変わってくるということだ。

これは場合分けの香りがする!!

 

だがしかし、1枚でも2桁を表すものがある。(10〜K)

これが入ってくると数字が一気に大きくなる気がする。

 ↓

じゃあいっそ、これも場合分けして後回しにしてしまえばよいのでは?

 

そんなかんじで、こんな場合分けが成された。

f:id:bluewindow:20141226012203j:plain

こうして考えた結果、とりあえず6桁までの数字(〜999,999)は全部自由に表現できるんじゃないかなーという気がした。

(図中で「全て表現可能」が消されていることについては次回になってから出てきますので、今日のところはちょっと辛抱してくださいまし)

 

 

それから、ここでちょっと楽しい武器を導入してみる。

それはRuby

 

念のため言っておくと、私はプログラミングをきちんと学んだことは一度もない。

ただ数年前、知人と話している時にほんの出来心から「プログラミングってできたらかっこよさそうだよね!」と言ってみたら「Macなら特に何も用意しなくてもターミナルでRubyが使えるよ」的なアドバイスをもらい、「じゃあやってみる!」とRubyに入門したことはある。

作りながら学ぶRuby入門 第2版

作りながら学ぶRuby入門 第2版

 

printを覚え、ifやwhileを覚え、配列やハッシュというものを…覚えた…んだっけ…?というところで私のRubyは止まっている。

約400ページの本には、80ページくらいのところにしおりが挟まれている。

 

と、そんなRubyレベルなので、武器と言っても大したことはできない。

ただ、初期課題として与えられた「素数判定」と「素因数分解」のプログラムは残っている。

超単純なプログラムではあるが、自分で作ったものというだけでものすごく愛着があり、またよく働いてくれるような気がしてしまうのは私だけではないはず。

 

ということで、この自作Rubyプログラムを使って、999,999までの素数の個数を求めることにした。

# 10から999999の間の素数の個数を求める
n = 0

for a in 10..999999
b = 2
while b * b <= a
 if a % b == 0 # aがbで割り切れた場合
  b = 2
  break
 else
  b = b + 1
 end
end

 if b == 2
  n = n
 else
  n = n + 1
 end
end

print n, "\n"

正直こんな文を見ても何をしているのかよく思い出せない←

けど確か、2以上の数で1個ずつ割って確認しているのだったはず。そして範囲が10〜となっているのは、たしかこのやり方では小さい数はうまいこと数えられないからである。

これを実行すると、78,494という答えが出てくる。これに9以下の素数(2, 3, 5, 7)の数を足すと、999,999以下の素数78,498個であることがわかる。

 

ここまでのまとめ

  • 場合分けするとちょっと取り組みやすくなる
  • Rubyよく覚えてないけど楽しい
  • 自分の作ったプログラムで出した数字は格別
  • 6桁以下の素数は全て表現可能 → 78,498個はOK!

 

ここまで考えて、だいたい1日目の22時過ぎくらい。

 

次回、今日の話が冒頭であっという間に否定されます。お楽しみに。