学部の演習課題が発掘されたので golang でやってみる。

エラトステネスの篩と呼ばれる素数を選別するアルゴリズムを用いて、4 桁の最小および最大の素数を求めよ。また、同様に 5 桁から 9 桁までの素数を求めよ。

エラトステネスの篩を用いて、任意の数値の素因数分解プログラムを作成し動作を検証せよ。

完全数を求めるプログラムを作成し、10000 以下の完全数を求めよ。完全数：その数を除く全ての約数の和がその数と同じになる数のこと。

友愛数を求めるプログラムを作成し、10000 以下の範囲で友愛数を求めよ。友愛数：異なる 2 つの自然数の組で、自分自身を除いた約数の和が、互いに他方と等しくなるような数のこと。

エラストテネスのふるい
エラストテネスは $\mathcal{O}(\sqrt{n})$ で $n$ までの素数を算出できるアルゴリズム。
多項式時間で解けるAKS 判定法などもあるが、プログラムの題材としてはこちらの方がわかりやすい。
エラストテネスのふるいを実装するにあたり、true で初期化された配列が必要なため、sieve := make([]bool, end+1) を作成した。
これにより、添字 0~end までを持つ配列ができる。
これを true で初期化するわけだが、単純にループを回すとそれだけで計算量が $\mathcal{O}(n)$ になってしまう。
そのため、copy をしていくことで、この部分の計算量を $\mathcal{O}(\log n)$ とした。
true と false(ここではその添字の数字が素数であるかの真偽値)を逆に考えればこの作業は必要ないが、感覚的に書けなくなるのが嫌なのでこのようにした。
素因数分解
素因数分解は入力値 $n$ までの素数で割っていくことで実装した。
golang には while がないので for で書いた。
完全数
完全数と友愛数に関してはその数の因数の和を保持して再利用したかったので構造体を作り、PrimeSolver.Memo に保存した。
prime とは言っているものの、使う先は完全数と友愛数なので命名がちょっと違う気もする。
メモの作成に $\mathcal{O}(n)$ かかるが、判定は $\mathcal{O}(1)$ でできる。
友愛数
完全数と PrimeSolver を共有している。
英訳を調べると Amicable と出てきたが合っているかわからない。
友愛数がない場合は err でうまいこと処理したかったが、いまいちよくわからなかったのでこんな実装になっている。
また、return nil, ~~~ と書けなかったので 0, ~~~ を返している。(エラーハンドリングするから多分デフォルト値みたいなもので大丈夫だと思っている)

普段 python で書いているので i ** 2 ができないなどの若干つまづく場面はあった。
文法が完結で比較的書きやすいと思う。
若干納得がいかない点もあるが‥。

関数がキャメル(fmt.Println が面倒、println もあるから補完が効きにくい)
1 文字変数の推奨(補完されるしそこまで短くしなくてもいいのでは？　)

golangで学部の演習をする

{{ page.title }}