The prime factorization of an integer tells us which prime numbers build it.
From that factorization, there are two common ways to count prime factors:
\(\omega(n)\), the number of distinct prime factors, and \(\Omega(n)\), the total number of prime factors counted with multiplicity.
1. Prime factorization
Every integer \(n\ge2\) can be written uniquely as a product of prime powers:
\[
\begin{aligned}
n &= p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},
\end{aligned}
\]
where \(p_1,p_2,\ldots,p_k\) are distinct prime numbers and \(e_1,e_2,\ldots,e_k\) are positive integers.
2. Distinct prime factors: \(\omega(n)\)
The function \(\omega(n)\) counts how many different prime numbers appear in the prime factorization.
If
\[
\begin{aligned}
n &= p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k},
\end{aligned}
\]
then
\[
\begin{aligned}
\omega(n) &= k.
\end{aligned}
\]
The exponents do not affect \(\omega(n)\). A prime contributes \(1\) to \(\omega(n)\) as soon as it appears at least once.
3. Prime factors with multiplicity: \(\Omega(n)\)
The function \(\Omega(n)\) counts every repeated prime factor.
In exponent form, this means adding all the exponents:
\[
\begin{aligned}
\Omega(n) &= e_1+e_2+\cdots+e_k.
\end{aligned}
\]
For example, \(2^3\) contributes \(3\) to \(\Omega(n)\), because \(2^3=2\cdot2\cdot2\).
4. Worked example: \(360\)
Factor \(360\):
\[
\begin{aligned}
360
&=2\cdot180\\
&=2\cdot2\cdot90\\
&=2\cdot2\cdot2\cdot45\\
&=2^3\cdot3^2\cdot5.
\end{aligned}
\]
The distinct prime bases are \(2\), \(3\), and \(5\). Therefore:
\[
\begin{aligned}
\omega(360)&=3.
\end{aligned}
\]
The exponents are \(3\), \(2\), and \(1\). Add them:
\[
\begin{aligned}
\Omega(360)
&=3+2+1\\
&=6.
\end{aligned}
\]
So \(360\) has \(3\) distinct prime factors and \(6\) prime factors counted with multiplicity.
5. Difference between \(\omega(n)\) and \(\Omega(n)\)
| Number |
Prime factorization |
\(\omega(n)\) |
\(\Omega(n)\) |
| \(12\) |
\(2^2\cdot3\) |
\(2\) |
\(3\) |
| \(36\) |
\(2^2\cdot3^2\) |
\(2\) |
\(4\) |
| \(360\) |
\(2^3\cdot3^2\cdot5\) |
\(3\) |
\(6\) |
| \(97\) |
\(97\) |
\(1\) |
\(1\) |
| \(1024\) |
\(2^{10}\) |
\(1\) |
\(10\) |
6. Prime numbers
If \(n\) is prime, then its prime factorization is simply
\[
\begin{aligned}
n &= n.
\end{aligned}
\]
Therefore:
\[
\begin{aligned}
\omega(n)&=1,\\
\Omega(n)&=1.
\end{aligned}
\]
For example, \(97\) is prime, so \(\omega(97)=1\) and \(\Omega(97)=1\).
7. Square-free numbers
A positive integer is square-free if no prime factor is repeated.
In prime factorization language, every exponent is \(1\).
Example:
\[
\begin{aligned}
30 &=2\cdot3\cdot5.
\end{aligned}
\]
Since no prime repeats:
\[
\begin{aligned}
\omega(30)&=3,\\
\Omega(30)&=3.
\end{aligned}
\]
For square-free numbers, \(\omega(n)=\Omega(n)\).
8. Repeated-prime numbers
If a number has repeated prime factors, then \(\Omega(n)\) is larger than \(\omega(n)\).
For example:
\[
\begin{aligned}
72 &=2^3\cdot3^2.
\end{aligned}
\]
Here:
\[
\begin{aligned}
\omega(72)&=2,\\
\Omega(72)&=3+2=5.
\end{aligned}
\]
9. Negative integers
Prime factorization is usually defined for positive integers greater than \(1\).
For a negative integer, we factor out \(-1\) first:
\[
\begin{aligned}
-360
&=-1\cdot360\\
&=-1\cdot2^3\cdot3^2\cdot5.
\end{aligned}
\]
The factor \(-1\) is not prime, so the prime-factor counts come from the positive part:
\[
\begin{aligned}
\omega(-360)&=\omega(360)=3,\\
\Omega(-360)&=\Omega(360)=6.
\end{aligned}
\]
10. Why \(0\), \(1\), and \(-1\) are special
The number \(0\) does not have an ordinary prime factorization because it is divisible by every positive integer.
The numbers \(1\) and \(-1\) are units, not primes, and they have no prime factors.
Therefore, \(\omega(n)\) and \(\Omega(n)\) are not usually defined for \(0\), \(1\), or \(-1\) in elementary prime-factor counting.
11. Full calculation method
To compute \(\omega(n)\) and \(\Omega(n)\):
- Factor \(n\) into primes.
- Write the prime factorization in exponent form.
- Count the number of different prime bases to get \(\omega(n)\).
- Add all exponents to get \(\Omega(n)\).
12. Formula summary
| Quantity |
Formula |
Meaning |
| Prime factorization |
\(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\) |
Write \(n\) as a product of prime powers |
| Distinct prime factors |
\(\omega(n)=k\) |
Count different prime bases |
| Prime factors with multiplicity |
\(\Omega(n)=e_1+e_2+\cdots+e_k\) |
Count repeated prime factors too |
| Prime input |
\(\omega(p)=1,\ \Omega(p)=1\) |
A prime has exactly one prime factor |
| Square-free input |
\(\omega(n)=\Omega(n)\) |
No prime factor repeats |
13. Common mistakes
- Confusing \(\omega(n)\) with \(\Omega(n)\).
- Counting \(2^3\) as one factor when computing \(\Omega(n)\); it contributes \(3\), not \(1\).
- Counting repeated primes more than once when computing \(\omega(n)\).
- Counting \(1\) or \(-1\) as a prime factor.
- Stopping the factorization before all factors are prime.
Key idea: \(\omega(n)\) counts different prime names; \(\Omega(n)\) counts every prime copy.
