エラトステネス‐の‐ふるい〔‐ふるひ〕【エラトステネスの×篩】
エラトステネスの篩
エラトステネスの篩
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/19 06:15 UTC 版)
既に知っている素数で割れる自然数を数表から篩い落とすことで新たな素数を順次決定していく操作はエラトステネスの篩として知られている。ゆえに、知っている素数で割れない自然数全体の集合を指定する方法が与えられることと、このエラトステネスの篩にかけることとは等価である。 集合を指定する方法の一つは、その指示函数を与えることである。いま、p1 から pk が素数として決定されたものとし、そのような素数全部の積を P とする。また、自然数 n と P との最大公約数を (n, P) と表せば、n が決定済みの素数で割れることと、(n, P) > 1 となることとは同値である。このとき、十分大きな自然数 N を考え、N 以下の自然数 n のうち、決定済みの素数 p1, ..., pk で割れない自然数全体の集合を E とおくと、基本公式によって E の指示函数 χE は χ E ( n ) = ∑ d ∣ ( n , P ) μ ( d ) {\displaystyle \chi _{E}(n)=\sum _{d\mid (n,P)}\mu (d)} で与えられることがわかるから、これをエラトステネスの篩のメビウス函数を用いた表現と考えることができる（手続きとしては、χE(n) を計算することは知っている素数で順番に割っていくことに他ならないから、単に表現の仕方を変えただけである）。特に、χE(n) = 1 を満たす最小の n を pk+1 とすればこれは新しい素数であり、再び同様の手続きにしたがって次々に素数を決定することができる。
※この「エラトステネスの篩」の解説は、「メビウス関数」の解説の一部です。
「エラトステネスの篩」を含む「メビウス関数」の記事については、「メビウス関数」の概要を参照ください。
「エラトステネスの篩」の例文・使い方・用例・文例
エラトステネスの篩と同じ種類の言葉
- エラトステネスの篩のページへのリンク
