プログラマ脳を鍛える数学パズルQ3：カードを裏返せを解いてみた

プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問（増井 敏克）｜翔泳社の本 のQ3を解いてみました。

まずは、ルールを整理してみます。 最初はすべてのカードが裏なので、初期値を-1として、表になればカードナンバーを表示することにします。

この辺で約数に関係するということに気付きます。 素数は1と自分自身の2つしか約数が無いので、自分自身の番で1度だけ表になります。 そこから考えると、 約数が偶数個であれば、最後は表になり、奇数個であれば裏で終わることになります。

なので、解答

# 約数の数が奇数である数字を出力する
def main
  (1..100).each do |num|
    print num, ",\s" if count_in_divisor(num).odd?
  end
end

# 約数の数を計算する
def count_in_divisor(num)
  (1..num).select { |i| (num % i).zero? }.size
end

main

これでもいいのですが、 例えば20という数字の約数を考えるとき、20の1/2の10を超えれば、あとは自分自身しか約数はありません。 そこを考えて実装すれば、計算量が半分程度で済みそうです。

# 自分自身以外の約数が偶数個であれば良い
def main
  (1..100).each do |num|
    print num, ",\s" if count_in_divisor(num).even?
  end
end

# 自分自身以外の約数の数を計算する
def count_in_divisor(num)
  (1..num / 2).select { |i| (num % i).zero? }.size
end

main

ここでもう少し考えてみると、 約数の数が奇数になるときというのは、どんな時でしょう？ もう一度20に登場してもらうと、

20 = 1 * 20 = 2 * 10 = 4 * 5

という風に、ふつうは約数はペアになるので、約数の数は偶数です。

約数の数が奇数になるのは

25 = 1 * 25 = 5 * 5　

のように、平方数の時だけです。 ここまでくると、コーディングする必要もなさそうですが、 あえて書くなら

# 約数の数が奇数になるのは平方数の時のみなので、
# 100以下の平方数を出力する
(1..10).map { |n| print "#{n**2}, " }

でしょうか。

答え

$ ruby 03.rb
1, 4, 9, 16, 25, 36, 49, 64, 81, 100,