合成数列の和 Advent Calendar 2018 bash 編

注意: 「合成数列の和 Advent Calendar 2018」の9日目の記事になります。

詳細な問題内容はアドベントカレンダーの該当記事に譲るとして、ごく簡単にまとめておくと「100以下の自然数nが与えられたとき、1番目からn番目までの合成数の和を求めなさい」というもの。本記事ではbash編で、回答は以下の通りです。

qiita.sh

#!/bin/bash
n=$1
yes | awk '{print NR}' | factor | awk 'NF>2{print NR}' | head -${n} | paste -sd+ | bc

これをqiita.shとして保存し、実行した結果は次の通りになります。

$ bash qiita.sh 2
10
$ bash qiita.sh 4
27
$ bash qiita.sh 10
112
$ bash qiita.sh 100
7059

---

以下は簡単な解説になります(´・ω・)

yes | awk '{print NR}'ですが、ここでは上限を設けず、自然数の数列を生成しています。awkのNRは現在読み込んでいる行の行番号を保持する組み込み変数で、行を読み込むたびに1,2,3,...と増えていきます。そして「読み込む」ための行を生成するためにyesコマンドを利用しています。(参考:「上限を設けずに整数列を生成したい」)

factorは与えられた入力を素因数分解するコマンドで、その出力形式は次のようになっています。

$ seq 1 10 | factor
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
10: 2 5

ところで合成数とは「2つ以上の素数の積で表される数字」と定義することができ、上記の例では4,6,8,9,10が合成数であるといえます。つまりfactorの結果が3列以上になるものが合成数であり、それをawk 'NF>2{print NR}'でフィルタリングしています。

headは入力の先頭N行を標準出力に返すコマンドで、ここで「N番目までの合成数」を確定させています。

「N番目までの合成数」が確定したところで、これを合計する必要があります。awkを利用するのが一般的だと思いますが¹、せっかく(?)なので別の方法を採用しました。pasteコマンドの-sオプションは標準入力から入力されたすべての行を結合して1行にするもので、結合時のデリミタは-dオプションで指定します。つまりpaste -sd+では、入力される改行区切りの数列を+区切りに変換するということで、たとえば4+6+8+9+10というような結果を得ることができます。あとはこれを計算式として評価するだけなので、bcコマンドに食わせています。

1. 例: awk '{sum += $0} END{print sum}' ↩