今回はオイラーのφ関数です.
ベタな組み方でも処理に大きな問題のない内容でした.
※価格は記事執筆時のものです. 現在の価格はApp Storeから確認ください.
レビュー時のバージョン ： v2.1.1
スポンサーリンク
オイラーのφ関数
オイラーのφ関数とは, 自然数 に対して,
から
までの自然数に対して
と互いに素であるものの個数を与える関数です.
例えば 以下の自然数で
と互いに素である自然数は
の
個なので,
となります.
φ関数については, 自然数 や素数
, 指数
について以下の性質を持っていますが今回は用いず, 素直に1から順に最大公約数を確認します.
フロー
まず m に相当する値を用意し, カウンタ用に同時に変数 n にも代入します.
またφ関数の結果としてのカウンタ変数 φ(初期値0) も用意します.
以降は入力を要求で与えた数だけ, m自身とカウンタ変数nとが互いに後であるかをユークリッドの互除法である関数を実行して確かめます.
互いに素である時のみ変数φに1を足します.
互いに素であるかどうかの「次の場合」を抜け, n を1つ減らします.
これでループが抜けたときには変数 φ には φ(m) の値となっていることになります.
実行
実行して結果が正しいことを確かめます.
〆
これもまた無駄な処理が多いため, 値が大きくなると弱いです.
素因数分解して最初に紹介した性質を使った方が現実的でしょうね.
