初学者によるプログラミングMemo #22 素因数分解

#はじめに
今回は素因数分解のお話です
最近問題を解くことが多くなって、アルゴリズム関係に面白みを見出しています
Rails関係なくても書いている下記はすでに決まり文句ともなりました
なお、本記述はMacにおいて、Railsでの開発を前提としています
また、まだまだひよっこですので、不備等ございましたらご指摘いただけると幸いです→よく間違えますが、生暖かく見守ってくださると幸いです
＊例により、スマートなコードがコメント欄に乗っていますので、是非そちらもご参照ください
私の記事は、皆さんのご指摘・ご教示の上で成り立っています、ありがとうございます

#目次

• 素因数分解とは
• 問題を解いてみる

##素因数分解とは
素因数分解とは、ある正の整数を素数の積で表すことです
なんのこっちゃですかね？
具体的に見てみましょう
例えば「30」を素因数分解してみましょう

.rb

30 = 10 * 3
10 = 5 * 2
# ↑を合わせるとこう（↓）なる
30 = 2 * 3 * 5

2,3,5はいづれも素数ですね
このように、元の数を素数を使った掛け算で表すことを、素因数分解と言います

問題を解いてみる

さて、本題です
素因数分解を用いた問題を解いてみましょう

問題
"27156"の約数のうち、"100"以下の約数を全て答えよ
さあ、困った
なんせ約数の話は一切していないですからね
まあでも約数は小学生の範囲なんで割愛します、流石にわかるでしょうから

さて、お察しかと思いますが、素因数分解を利用することで、約数を求めることができます
順番にやっていきましょう
なお今回は、前々回の素数の話を使いますので、先にご覧になることを推奨します
メソッドはここに載ってます

.rb

#挙動確かめるために"20"で行います
require 'prime'

20.prime_division.each do |prime|
  p prime
end

# => [2, 2]
#    [5, 1]

prime_divisionメソッドを使うと、素因数分解を自動で行ってくれます便利ですねー、いや、本当にありがたい
で、返り値はご覧の通り、"[素数,その数]"となります
ではこの性質を利用してみましょう

.rb

require 'prime'

primes = []

20.prime_division.each do |prime|
  prime[1].times {primes << prime[0]}
end

p primes
# => [2, 2, 5]

素因数分解ができてますね
解説します
先ほどの返り値を元に、"primes"に"prime[0]"(素数自体)を代入しています
しかし、それだけでは1回しか代入されないので、その前に"times"メソッドを使って、"prime[1]"(素数の数)の回数分代入処理を行ってやります
これで、無事素因数分解ができました
あとは約数を作らないといけませんね

###約数を作る
さて、問題ももう後半に差し掛かりました
あとはこれを組み合わせてあげれば約数が出ますね
そうです組み合わせです
書いていきましょう

.rb

require 'prime'
primes = []
divisors = []

20.prime_division.each do |prime|
  prime[1].times {primes << prime[0]}
end
1.upto(primes.size) do |i|
  primes.combination(i) do |prime|
    divisors << prime.inject{|a,b| a *= b}
  end
end

p divisors

# => [2, 2, 5, 4, 10, 10, 20]

先に挙動の解説をします
"combination"メソッドを使って、組み合わせを作ります
組み合わせる数は"primes"に入っている要素分行うので、その前に、"upto"メソッドを使って、数を回します
"prime.inject{|a,b| a *= b}"は、組み合わせで持ってきた各項を掛け算してもらうための処理です

うまいこといきまし…ん？
なんかおかしいですね、２点ありますが何かわかりますか？

まず、"2"と"10"が2回出てきてしまっています

そして…

"1"がないですね

致命的です、これではいけません

###1がない
修正を加えます

.rb

require 'prime'
primes = []
divisors = [1] # <= ここ

20.prime_division.each do |prime|
  prime[1].times {primes << prime[0]}
end
1.upto(primes.size) do |i|
  primes.combination(i) do |prime|
    divisors << prime.inject{|a,b| a *= b}
  end
end

divisors.uniq! # <= ここ

p divisors

# => [1, 2, 5, 4, 10, 20]

これでいけましたね
"divisors = [1]"はなんか無理やり感があってあまり好きではないですが、仕方ありません（←成長を止める要因）
そして"divisors.uniq!"で、重複を削除しています

ここまでくればもう完成です

.rb

require 'prime'
primes = []
divisors = [1]
ans = []

27156.prime_division.each do |prime|
  prime[1].times {primes << prime[0]}
end
1.upto(primes.size) do |i|
  primes.combination(i) do |prime|
    divisors << prime.inject{|a,b| a *= b}
  end
end

divisors.uniq!
for i in divisors
  if i <= 100
    ans << i
  end
end

p ans

# => [1, 2, 3, 31, 73, 4, 6, 62, 93, 12]

できました
が、数字の並びが気持ち悪いので、"sort!"しましょう

###今回の完成形
ついでにおなじみの対話形式に変えちゃいましょう

.rb

require 'prime'

def divisor(x,y)
  primes = []
  divisors = [1]
  ans = []
  x.prime_division.each do |prime|
    prime[1].times {primes << prime[0]}
  end
  1.upto(primes.size) do |i|
    primes.combination(i) do |prime|
      divisors << prime.inject{|a,b| a *= b}
    end
  end
  divisors = divisors.uniq.sort
  for i in divisors
    if i <= y
      ans << i
    end
  end
  return ans
end

p "ある数の約数のうち、決まった数値以下の約数を求めたいん？そんなんうちに任しとき"
p "ほんならまず約数を求めたい数を教えてやー"
x = gets.to_i
p "ありがとう、次はなんぼ以下の約数求めなあかんか教えてや"
y = gets.to_i
if x != 0 && y != 0
  if x <= y
    p "なんでやねん！そんなん約数全部に決まってるやん"
    p divisor(x,y)
  else
    p "うちの労働力は高うつくで（笑）"
    p divisor(x,y)
  end
else
  p "もぅ、いけずせんと、ちゃんと入力して！！"
end

以上、終わり！！