線形ふるい法による素数、オイラー関数、メビウス関数の高速計算
線形ふるい法 (Linear Sieve)
線形ふるい法は、ある範囲内の素数を効率的に求めるアルゴリズムです。このアルゴリズムの時間計算量はO(n)であり、各合成数が一度だけふるい落とされることを保証します。本稿では、線形ふるい法を用いて素数、オイラー関数、メビウス関数を計算する方法を解説します。
1. 素数の線形ふるい
素数の線形ふるいは、指定された上限Nまでのすべ ...
5月19日 07:09 投稿
奇想天外なアイデアがコードで現実になる場所
5月19日 07:09 投稿