【無料公開中!】素因数分解で学ぶruby

2018.4.18 追記--------------------------

やっぱりいろんな人に見てもらいたいという思いから、期間限定で無料公開しています!! このnoteがいいなと思ったらぜひTwitter等でシェアしていただきたいです。やってみた感想や質問、またこのnoteへのサポートもお待ちしております。

-----------------------------------------

こんにちは!普段はruby on railsとreactで幅広くフロントエンドからバックエンドまで開発をしているエンジニアの竜太朗です。

最近流行りのプログラミングの簡単なチュートリアルを書いてみました。他のチュートリアルと同じことをしても面白くないので、僕がプログラミングが始めたときに一番難しいと感じた、どこが間違ってるのかを調べる方法(=デバッグ)についても解説しています。

ちょっとくどくデバッグを解説してしまっていますが、やり方を具体的に説明するために必要なことなので、我慢してお付き合いください。わかってるって人はどんどん飛ばしてもらって大丈夫です。

簡単とは言っても全くプログラミングを触ったことのない人には少し難しいかもしれません。rubyの基礎文法や実行の仕方が分かっていないと少し辛いと思います。ドットインストールやprogateで勉強してから、その次のチュートリアルとして使ってもらえればと思います!

一番僕のおすすめのrubyの入門書は現役エンジニアの迫くんが書いたnoteです!昨日発売されて飛ぶように売れているらしいのですが、図解の丁寧さがすごくてめっちゃ分かりやすいです!

このチュートリアルでは、素因数分解クラスを実装して理解が難しいオブジェクト指向を解説していこうと考えています。インスタンスが何か、メソッドとは何かの理解も深まるような記事にしてあります。

チュートリアルの構成


デバッグとは
素因数分解をプログラミングで表現する
とりあえず動く素数判定を作る
キーボードからの入力を受け取る
素数判定を高速化する
素数判定関数を定義する
素因数分解クラスの実装
素数の配列を取得する
素因数分解を実装する(近日公開!)

となっています。肝心の素因数分解はまだ実装できないですが、すぐに完成させようと思っています。では、さっそくはじめていきましょう!

デバッグとは

先ほども書いたのですが、デバッグとはどこが間違っているのかを探すことをさします。プログラミングの一番やっかいなところなのですが、少しでも間違っているとエラーが出たり、思っていたのと違う結果が出力されることが極めて頻繁にあります。というか、これにほとんどの時間を取られるといっても過言ではありません。

エラーが間違っているところを直接指定してくれたらいいのですが、全然違うところでエラーが出ていてそこはあってるのに、なんで!?ってなることもあります。思ってた値と違う値が出力されてしまうと、どこから間違っているのかすらわけわからなくなってしまいます。

そういうときに、こんな感じでデバッグするとだいたい解決するよ、ってことを紹介したいと思います。基本的に処理を細かく分けてどこまで正しい計算や処理がなされているかを、そのときの変数の値を出力することで把握してきます。

このように問題を細分化して論理的に考える能力は、プログラミングだけでなく多くの分野で役に立つので、最初は難しいですが頑張って習得することをオススメします!

素因数分解をプログラミングで表現する

いきなりプログラミングで素因数分解をしようとしてできるならこの記事を読む必要はないでしょう。まずは素因数分解をプログラミングで表現するために何が必要か考えてみましょう。素因数分解とは、その数字までの素数で何回割れたかをその素数同士の積で表したもです。

コンピュータは私たちと違って何回も計算すること(ループ処理)が得意です。つまり、素因数分解したい素数の配列さえ取得できてしまえば、あとはその配列でループを回してそれぞれの素因数がいくつ含まれているかを取得して終わりです。

では、どのようにして、素数の配列を取得しましょう。素数の一覧があるサイトから取得してもいいのですが、ここでは自分で素数判定のコードを書いてしまいましょう。

次は素数をどのように判定するかをするかを考えてみます。素数の定義は、

1 より大きい自然数で、正の約数が 1 と自分自身のみであるもののこと

です。(wikipediaより)つまり、この定義の通り1から自身の数字まで割ってみて何回割り切れたかをカウントしてやればいいことになります。これもループ処理を使えば簡単に実装できます。

とにかく動く素数判定プログラムを作る!

上の説明で、実際にどのようにコードを書いていけばいいかはわかったと思います。そして、関数やオブジェクト指向がわかっていなくても、一瞬でかけてしまいます。さあ、答えを見る前に自分なりのコードを書いてみましょう!

どうですか?書けましたか?いきなり答えをみてしまうと思考停止しちゃうので自分なりの答えを出すことはとても大切です。だからといって全く思い浮かばなかった人は先に進んでください。詰んでしまって面白くない、と感じてしまうのが一番もったいないです。

では、コードを解説していきましょう!

はじめは、判定する数字を固定しましょう。ご安心を。あとでキーボードから入力を受け取って動的に判定できるコードに進化させますから。

# target: 素因数分解したい数字。最初は7で固定します。
target = 7
# count: 何回割り切れたかを数える数字。1なら素数。最初は0で初期化。
count = 0

これで、準備は整いました。では、実際にループを回して何回割り切れるかを判定してみましょう。1からtarget - 1 までの全ての数字でtargetを割ってみます。

for i in 1..target
 if target % i == 0   # %はあまりを計算するプログラミング独特の記法
   count += 1         # countを1大きくする
 end
end

そして、countの値に応じて出力を切り替えます。

if count == 1                # == は値が一致していることを示す。
 p "#{target}は素数です。"      # #{"変数名"}は文字列の中で変数の値を展開する書き方
else
 p "#{target}は合成数です。"
end

実行してみると、、

$ ruby soinsubunkai.rb 
7
"7は合成数です。"

!?こいつバカなんじゃねーの!?はい、違います。これをミスに気づかずに実行してしまった僕がバカなんです。

じゃあ、どこが間違っていたのか。わかりますか?僕は一箇所だけ自信がなかったのですぐにそこだとわかりましたが、勉強を始めたばかりだとどこが間違ってるのか検討もつかないかもしれません。

そこで、デバッグの方法を具体的に紹介したいと思います。

まずcountに思い通りの値が入っていないだろうなということは検討がつきます。なぜかというと、出力の際のifが思った方と反対の条件分岐になってしまっているからです。初めからコードを見直すよりも、おかしくなったところから遡った方が圧倒的に早く原因を見つけられます。

怪しいものはとりあえず出力してみましょう。

if count == 1
 p "#{target}は素数です。count: #{count}"
else
 p "#{target}は合成数です。count: #{count}"
end

# 出力
7は合成数です。count: 2

なるほど、countが思ってたより1大きい。1〜6までの数字全部で7を割ったら1以外割り切れないはずなのに、おかしい。次に、この「はず」を疑ってみましょう。

for i in 1..target
 p i                  # iが何なのかを出力して調べてみる
 if target % i == 0
   count += 1
 end
end

実行してみたらわかると思うのですが、7まで出力されています。原因は、

1..target

が1〜6ではなく、1〜7という仕様だったことでした。あくまでデバッグの具体的な手法を紹介するための具体例なので、くどくなってしまいましたがこの問題を細分化して考えるというのはデバッグでとても重要です。これぐらいなら調べたらわかると思うかもしれませんが、これなんて調べますか?笑

僕はなんて調べたらいいかわからなかったので、実際にiを出力してみました。実際に調べてもらったらわかるんですけど、「1..i ruby」じゃ検索うまいことできないんですよ。そんなこと考えてる間にデバッグしたら解決できます。

では、修正しましょう。

target = 7
count = 0
for i in 1..target
 if target % i == 0
   count += 1
 end
end

if count == 2                # ここを修正
 p "#{target}は素数です。"
else
 p "#{target}は合成数です。"
end

出力してみると、うまくいっていることがわかると思います。

そうなんです。素数判定をするぐらいならすぐ書けちゃうんです。

キーボード入力から数字を受け取る

これまでのコードでは、プログラム上に記載した数字しか判定できなかったですよね。それでは、あまりにも実用性がないので、キーボード入力から数字を受け取れるようにしましょう。

こんな記述滅多にしないので普通にgoogleで検索しました。全部覚えるなんて無理です。

こんな感じで実現したいことを言語化して検索できるのもプログラミングをする上でとても重要です。一番上の結果で答えがわかります。ふむふむ、getsというものを使えばいいんだ。さっそくやってみましょう。

target = gets

に変更して、実行!

$ ruby soiusubunkai.rb 
100
soiusubunkai.rb:3:in `<main>': bad value for range (ArgumentError)

ファイルを実行すると入力待ちになるので100と入力してEnter。すると、エラーが出てしまいました。よくわからないので、とりあえず、targetの中身を調べてみます。さっきと比べて変わったのってここだけだから。

target = gets
p target
# count = 0
# for i in 1..target
#  if target % i == 0
#    count += 1
#  end
# end
#
# if count == 2
#  p "#{target}は素数です。"
# else
#  p "#{target}は合成数です。"
# end

さっきまでの判定の部分はエラー出ちゃうから一旦コメントアウト。そして、実行してみます。

$ ruby soiusubunkai.rb 
100
"100\n"

なにやら色々無駄なものがいっぱいついて出力されていますね。何が起こっているのかを説明すると、100という文字が出力されているのです。最後の\nは改行文字といって、その後に改行しますよって意味です。

なぜエラーが出たかというと、1から"100\n"までの数字っていう訳のわからないものを定義しようとしたからです。これを数字の100にするにはメソッドを二つ使えばいいのですが、その説明はあとに譲るとして一旦以下のおまじないを添えといてください。

target = gets.chomp.to_i

これで、先ほどのコメントアウトを戻すと正常に動くことが確認できると思います。いろんな数字で試してみてください。

素数判定を高速化する

勘の鋭い人は気づいたかもしれないですが、実は先ほどのコードかなり無駄な処理を実行してしまっているんです。そうです、わざわざtargetの数字まで割らなくてもtargetの半分まで確認したら十分なんです。36で考えると、18以降はどの数字でも割れないなんて自明です。では、やってみましょう。

for i in 1..target / 2       # ここを修正
  if target % i == 0
    count += 1
  end
end

if count == 1                # ここも修正
  p "#{target}は素数です。"
else
  p "#{target}は合成数です。"
end

たったこれだけです。4桁ぐらいだと違いがわからないと思うのですが、6桁あたりから、パソコンのスペックによっては違いが実感できるのではないでしょうか。僕は、10000000でやってみたらかなり違いが実感できました。

もう一つ、高速化する方法を紹介しましょう。これは、合成数を素早く判定するアルゴリズムなのですが、countが2より大きくなった時点で合成数であることは確定していますよね?そこで、2を超えた時点でループを抜けるようにしてあげましょう。

for i in 1..target / 2
 if target % i == 0
  count += 1
 end
 break if count >=2  # この1行を追加。後置ifといい条件が真のときのみifより前を実行
end

これで、かなり合成数の判定が速くなったと思います。とくにさっきの10000000はパソコンのスペックによらず爆速で合成数と判定できるでしょう。

ではこれが、最速なのでしょうか?実はもっと速くする方法があるんですね。こういうのを考えるのも好きな人もいると思うので、あえてここに答えは書かないことしにします。googleで検索してみるか、僕にこっそりDMを送ってきてください。ヒントは、ループの回数をもっと少なくできます。もしかしたら、僕の知らない高速化の手法もあるかもしれないです。

2018.4.18追記-------------------

実際に実装してみたのですが、一つ目は計算回数の桁が半分になります。もう一つは、計算回数が1/3ぐらいになります。一個目は特にビビるぐらい計算が早くなりました。

---------------------------------

素数判定関数を定義する

だんだんプログラミングっぽくなっていきます。素数判定の関数(=メソッド)を定義してみましょう。ここでは素数を渡す(=引数)と、素数かどうかのtrueかfalseを返す関数にしましょう。名前はis_prime_numberとしてみましょう。is_...で始まることで名前をみただけでtrueかfalseで返ってくるんだなということが分かりやすくなります。

こうしないといけないということはないのですが、こうすることで他の人が読んだときに分かりやすいコードになります。日本語も基本的には使うのを避けることが一般的です。ちなみに素数は英語でprime numberです。つまり、is_prime_numberは「素数かどうか」という意味です。一歩先のかっこいいコードをかけるようになりましょう!

def is_prime_number(target)
 count = 0
 for i in 1..target / 2
   if target % i == 0
    count += 1
   end
   break if count >=2
 end

 return count == 1
end

rubyでは、returnを書かなくても最後の計算が返り値として得られるのですが、ここでは明示的にreturnを書いて素数かどうかを判定した結果、すなわちcountが1かどうかのtrue/falseを返しています。

では、この関数を使ってみましょう。

is_prime_number(target) ? p("#{target}は素数です。") : p("#{target}は合成数です。")

# if is_prime_number(target)                # ここを修正
#   p "#{target}は素数です。"
# else
#   p "#{target}は合成数です。"
# end

少し書き方を変えてみました。これは三項演算子と呼ばれるもので、

条件  ?  条件がtrueのときの処理  :  条件がfalseのときの処理

という書き方です。下のコメントアウトと同じ意味なのですが、1行でかけてスッキリするのでよく使われます。最初は慣れないでしょうから、そういう書き方もあるんだと思っておけば大丈夫です!

ちなみに、p("出力")というふうに変更したのはエラーが出たからです。

p "出力"
p("出力")

上の二つは同じ意味なのですが、単体で使うとき以外は下の書き方にしないとエラーが出てしまうようです。

素因数分解クラスの実装

いよいよオブジェクト指向っぽくなってきました。まずは、クラスについて説明します。クラスとは処理(=メソッド)をまとめたものです。概念だけでは分かりにくいので、素因数分解クラスを考えてみましょう。素因数分解クラスは、先ほど作った素数判定のメソッドや、これから実装するその数字までのそうすを取得するメソッド、素因数分解をするメソッドを持っています。

じゃあ、このメソッドはいつでも使えるのかというとそうではありません。このメソッドを使うことのできる対象をオブジェクト(=インスタンス)と言います。このインスタンスはrubyのハッシュのような形で、いくつものデータを格納しておくことができます。

今回でいうと、対象となる数字(=target)やその数字までの素数(=prime_array)を格納しています。これでぼんやりとイメージが掴めたかと思います。それでは実装していきましょう。

この中に格納されているそれぞれの変数をインスタンス変数と呼び、@変数名という書き方をします。これは、クラス内ならどこでも呼び出すことが可能です。

インスタンスを新しく作ったときに一回だけ呼ばれる特別なメソッドがあります。これがinitializeメソッドです。今回でいうと素因数分解の対象となる数字を最初に設定したいので、initializeの中で@targetというインスタンス変数に格納します。@prime_arrayも初期化しておきます。

class Factoring
 def initialize(target)   #初期化のメソッド
   @target = target       #インスタンス変数
   @prime_array = []      #インスタンス変数
 end

 def is_prime_number
   count = 0
   for i in 1..@target / 2
     if @target % i == 0
      count += 1
     end
     break if count >=2
   end

   return count == 1
 end

これだけです。ほぼ先ほどのメソッドをコピーしただけですが、引数をわたさなくても@targetに欲しい数字が格納されているので、そのあたりを少し変更しています。ではインスタンスを作ってみましょう。

target = gets.chomp.to_i
factoring = Factoring.new(target)

これは独特の書き方で慣れないかもしれないですが、インスタンスを新規作成するメソッドなんだと思っておいてください。では、実行してみましょう。

soiusubunkai.rb:20: syntax error, unexpected end-of-input, expecting keyword_end

上のようなエラーが出たんではないでしょうか。これは多分rubyで一番よく出るエラーだと思います。日本語に直してみると、「endある思ったのに、endないやんけ!」って言ってます。確かに、classのendが抜けていました。これを実行する前に気づいていた人がいたら鋭いですね。

class Factoring
 def initialize(target)
   @target = target
 end

 def is_prime_number
   count = 0
   for i in 1..@target / 2
     if @target % i == 0
      count += 1
     end
     break if count >=2
   end

   return count == 1
 end
end                      # このendが抜けてた

では、気を取り直して実行してみましょう。

何も起こらなければ成功です。宣言しただけですからね。では今度は、素数判定をしてみましょう。

target = gets.chomp.to_i
factoring = Factoring.new(target)
p factoring.is_prime_number

これを実行してみると、

$ ruby soiusubunkai.rb 
100
false

いい感じですね。

素数の配列を取得する

ではどんどん実装していきましょう。素数かどうかの判定は、is_prime_numberメソッドを使えば簡単にできるので、素数のときに@prime_arrayに格納していくだけです!では、is_prime_numberの下に、get_prime_arrayメソッドを追加しましょう。確認用に、@prime_arrayを返すようにします。

class Factoring
 ...
 def is_prime_number
   ...
 end

 def get_prime_array
   for i in 1..@target
     @prime_array << i if i.is_prime_number
   end
 @prime_array
 end

end

target = gets.chomp.to_i
factoring = Factoring.new(target)
p factoring.get_prime_array

実行の仕方はこれまでと同じです。では、実行してみましょう。

$ ruby soiusubunkai.rb 
100
soiusubunkai.rb:20:in `block in get_prime_array': undefined method `is_prime_number' for 1:Fixnum (NoMethodError)
	from soiusubunkai.rb:19:in `each'
	from soiusubunkai.rb:19:in `get_prime_array'
	from soiusubunkai.rb:28:in `<main>'

また、エラーが出てしまいました。正直これは結構難しいです。覚悟して読んでください。笑

まず、is_prime_numberメソッドはFactoringクラスのメソッドです。そして、get_prime_arrayメソッド内でis_prime_numberを使おうとしているiはFactoringクラスのインスタンスではないです。だから、エラーが出ています。

もう少し厳密にいうと、ここでのiはFixnum(整数)クラスのインスタンスです。つまりこのエラーが言いたいことは、Fixnum(Integer)クラスにis_prime_numberは定義されてませんよってことです。(rubyのバージョンによってFixnumとIntegerクラスがあるようですがほぼ一緒と思ってもらって問題ないです。僕もこれを書いて初めて知りました。)

では、どのように直すといいでしょうか。二つの方法があります。一つは、Integerを引数に取る関数をFactoring内で定義してしまう、もう一つは、Integerクラスにis_prime_numberを追加する、です。今回は一個目の方法だけ説明しようと思います。興味がある人は二つ目も自分で調べてやってみてください。

それでは実装していきます。ここではprivateメソッドとして定義します。privateメソッドとは、クラス内からのみ参照が可能なメソッドです。private以下に書いたメソッドが自動的にprivateメソッドとして認識されます。

class Factoring
 def initialize(target)
   @target = target
   @prime_array = []
 end

 # 同じ名前の関数を使えないので変更。これはインスタンスが素数かどうかの判定するメソッド
 def is_prime_number? 
   is_prime_number(@target)
 end

 def get_prime_array
   for i in 1..@target
     @prime_array.push(i) if is_prime_number(i) # iが素数かどうか判定
   end
   @prime_array
 end

 private

 # ここまで実装してきた素数判定をprivateメソッドに。引数が素数かどうかの真偽値を返す。
 def is_prime_number(target)
   count = 0
   for i in 1..target / 2
     if target % i == 0
      count += 1
     end
     break if count >=2
   end

   return count == 1
 end
end

かなり変えました。is_prime_number(target)でtargetが素数かどうかを判定できるprivateメソッドを定義しています。それを使ってiが素数かどうか判定して、素数のときにだけ@prime_arrayにiを格納しています。これで@targetまでの素数を取得できました。さあ、素因数分解まであと一歩です!

と、言いたいところなのですが、今日は1万字近く書いてちょっと疲れたので、明日以降に更新していきます。

このnoteを気に入ってくださった方はぜひTwitte等で拡散していただけると嬉しいです。これからの更新の励みになります!

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

これでなんとか明日もあったかいご飯が食べれそう、、ありがとうございます
6

宮川 竜太朗

コメントを投稿するには、 ログイン または 会員登録 をする必要があります。