素因数の個数
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 22:49 UTC 版)
自然数 n の相異なる素因数の個数を与える関数を ω(n) と表記し、n の重複も含めた素因数の総数を与える関数を Ω(n) と表記する。n が n = ∏ i = 1 k p i α i = p 1 α 1 p 2 α 2 ⋯ p k α k {\displaystyle n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}}=p_{1}^{\alpha _{1}}p_{2}^{\alpha _{2}}\dotsm p_{k}^{\alpha _{k}}} (ただし p1, p2, ..., pk は相異なる素数、α1, ..., αk∈[1, ∞)⋂ℤ) と素因数分解されるとき、 ω ( n ) = k , {\displaystyle \omega (n)=k,} Ω ( n ) = ∑ i = 1 k α i = α 1 + ⋯ + α k {\displaystyle \Omega (n)=\sum _{i=1}^{k}\alpha _{i}=\alpha _{1}+\dotsb +\alpha _{k}} である。例えば、60 = 22・3・5 であるから、ω(60) = 3, Ω(60) = 2 + 1 + 1 = 4 である。 素因数は 2 以上であるから Ω ( n ) ≤ log n / log 2 = log 2 n {\displaystyle \Omega (n)\leq \log n/\log 2=\log _{2}n} が任意の n に対して成り立ち、等号はちょうど n が2の冪乗であるときに成り立つ。 また、ω(n) の増加の割合は以下の式で表される。 lim sup n → ∞ ω ( n ) log log n log n = 1. {\displaystyle \limsup _{n\rightarrow \infty }{\frac {\omega (n)\log \log n}{\log n}}=1.} より厳密には、以下の式が成り立つ。 ω ( n ) ≤ 1.38402 log n log log n ( n ≥ 3 ) , ω ( n ) ≤ log n log log n + 1.45743 log n ( log log n ) 2 ( n ≥ 3 ) , ω ( n ) ≤ log n log log n − 1.1714 ( n ≥ 26 ) . {\displaystyle {\begin{aligned}\omega (n)&\leq 1.38402\,{\frac {\log n}{\log \log n}}&(n\geq 3),\\\omega (n)&\leq {\frac {\log n}{\log \log n}}+1.45743\,{\frac {\log n}{(\log \log n)^{2}}}&(n\geq 3),\\\omega (n)&\leq {\frac {\log n}{\log \log n-1.1714}}&(n\geq 26).\end{aligned}}} 自然数における具体的な ω(n) の値についてはオンライン整数列大辞典の数列 A001221を、 Ω(n) の値はオンライン整数列大辞典の数列 A001222を参照。
※この「素因数の個数」の解説は、「素因数」の解説の一部です。
「素因数の個数」を含む「素因数」の記事については、「素因数」の概要を参照ください。
- 素因数の個数のページへのリンク