オイラーのトーシェント関数と線形ふるい法による計算
例えば、6のオイラーのトーシェント関数を求める場合：6=2×3なので、そのトーシェント関数は6×(2-1)/2×(3-1)/3となります。
原理：1~NのうちNと互いに素な数の個数は、NからNと互いに素でない数を引いたものに等しくなります。Nと互いに素でない数はNの因数の倍数によってふるい落とされますが、一部の数は複数の因数によって複数回ふるい落とされるため、因数の積の倍数を ...
6月15日 22:32 投稿
線形ふるい法による素数、オイラー関数、メビウス関数の高速計算
線形ふるい法 (Linear Sieve)
線形ふるい法は、ある範囲内の素数を効率的に求めるアルゴリズムです。このアルゴリズムの時間計算量はO(n)であり、各合成数が一度だけふるい落とされることを保証します。本稿では、線形ふるい法を用いて素数、オイラー関数、メビウス関数を計算する方法を解説します。
1. 素数の線形ふるい
素数の線形ふるいは、指定された上限Nまでのすべ ...
5月18日 22:09 投稿