= Prime omega function
{title2=$\omega(n)$}
{wiki}
The <prime omega function> $\omega(n)$ counts the distinct <prime factors> of a <positive integer> $n$, so it is the <cardinality> of the <prime support of an integer> $P(n)$. For a <prime factorization> with distinct <prime numbers> $p_1,\ldots,p_r$ and positive exponents,
$$
n=p_1^{a_1}\cdots p_r^{a_r}\quad\Longrightarrow\quad
\omega(n)=r=\sum_{p\mid n}1.
$$
At $n=1$ there are no <prime factors>, so the <empty sum> gives $\omega(1)=0$. The <total number of prime factors> instead gives $\Omega(n)=\sum_i a_i$. https://darijgrinberg.gitlab.io/floor.pdf[Darij Grinberg, MIT 18.781, Floor and arithmetic functions, Definition 2.1.2: distinct and repeated prime factors]{ref}
For $72=2^3\cdot3^2$, the <prime support of an integer> is $\{2,3\}$ and $\omega(72)=2$. The comparison examples give $\omega(30)=3$, $\omega(32)=1$ and $\omega(36)=2$. Raising an existing <prime factor> to a higher power does not affect the <prime omega function>: $\omega(p^k)=1$ for a <prime number> $p$ and $k\ge1$. Thus the <prime omega function> is a <strongly additive arithmetic function>, with
$$
\omega(ab)=\omega(a)+\omega(b)\quad\text{if }\gcd(a,b)=1.
$$
The reason is that <coprime integers> have disjoint <prime supports of an integer>. For arbitrary <positive integers>, their <prime support of an integer> combines by <set union>, and the shared <prime factors> are exactly those of the <greatest common divisor>. Counting this <set union> gives the more general identity
$$
\omega(ab)=\omega(a)+\omega(b)-\omega(\gcd(a,b)).
$$
For $a=12$, $b=18$, both <prime supports of an integer> are $\{2,3\}$ and $\gcd(a,b)=6$, so $\omega(216)=2+2-2=2$. In particular $\omega(4)=1\ne2=\omega(2)+\omega(2)$: the <prime omega function> is not a <completely additive arithmetic function>.
The <prime omega function> is useful for counting choices involving distinct <prime factors>. Every <squarefree divisor> of $n$ chooses a <subset> of its <prime support of an integer>, so there are $2^{\omega(n)}$ <squarefree divisors>. For $72$, this gives $2^2=4$, namely $1,2,3,6$. Also $\omega(\operatorname{rad}(n))=\omega(n)$, because the <radical of an integer> keeps exactly that <prime support of an integer>. The <total number of prime factors> records what this count discards, and the two counts agree exactly on <squarefree integers>.
Back to article page
