Is there a formula that can tell us how many distinct prime factors a number has? We have closed form solutions for the number of factors a number has and the sum of those factors but not the number of distinct prime factors.

So for example: \begin{array}{rr} \text{number} & \text{distinct}\atop \text{prime factors} \\ 1&0 \\ 2&1 \\ 3&1 \\ 4&1 \\ 5&1 \\ 6&2 \\ 7&1 \\ 8&1 \\ 9&1 \\ 10&2 \end{array}

  • $\begingroup$ What closed form solutions are you referring to? If you mean $d(n) = \prod_{p^r \| n} (r+1)$ then what is wrong with $\omega(n) = \sum_{p \mid n} 1$? $\endgroup$ – Erick Wong Jun 2 '13 at 23:25

This is a historically interesting question as it led Hardy and Ramanujan to lay the foundation to probabilistic number theory in course of their solution to this problem. Given $n$ there is no non-trivial deterministic closed form formula for the number of distinct prime factors of $n$. However we have very good probabilistic formula for the same.

Hardy and Ramanujan proved that for almost all integers, the number is distinct primes dividing a number $n$ is formula

$$ \omega(n) \sim \log\log n. $$

We can do much better than the Hardy-Ramanujan estimate and find and estimate of $\omega(n)$ which can be bounded by normal distribution. Erdos and Kac imporved the estimate of $\omega(n)$ and proved that

$$ \lim_{x \to \infty} \frac{1}{x}\# \Big\{n\le x, \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}} \le t \Big\} = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{t}e^{-\frac{u^2}{2}}du $$

This formula says that if $n$ is a large number, we can estimate the distribution of the number of prime factors for numbers of this range. For example we can show that around 12.6% of 10,000 digit numbers are constructed from 10 distinct prime numbers and around 68% (±$\sigma$) are constructed from between 7 and 13 distinct primes.

  • $\begingroup$ "for almost all integers, the number is distinct primes dividing a number $n$ is given by the asymptotic formula" does not make sense. Asymptotic formulas do not apply to individual instances; you wouldn't be able to cite a single number $n$ for which the formula gives its number of distinct primes. $\endgroup$ – Marc van Leeuwen Jun 3 '13 at 7:44
  • $\begingroup$ Yeah asymptotic is not the right word, but the result remains the same. This is a probabilistic result. $\endgroup$ – Nilotpal Kanti Sinha Jun 3 '13 at 8:16
  • $\begingroup$ I see nothing random at all in the formulation. $\endgroup$ – Marc van Leeuwen Jun 3 '13 at 8:21
  • $\begingroup$ Well then for a more precise formulation, you might want to refer to mathworld.wolfram.com/Hardy-RamanujanTheorem.html and mathworld.wolfram.com/Erdos-KacTheorem.html $\endgroup$ – Nilotpal Kanti Sinha Jun 3 '13 at 8:33
  • $\begingroup$ And that statement involves an expression $\sqrt{\ln\ln x}$, which cannot be taken out without the statement losing its meaning. $\endgroup$ – Marc van Leeuwen Jun 3 '13 at 8:37

This is commonly known as $\omega(n)$. See Wikipedia.


We do $not$ have the closed form solutions you claim. We have formulas that assume that we know the prime factorization.


If you want to calculate $\omega(n)$ for a large range of $n$, it's simple to modify the Sieve of Eratosthenes to count distinct prime factors. Instead of marking multiples of each prime, keep a counter for every number and increment instead of marking. SO code example


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.