Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Given an integer $n$, I want to know the asymptotic order of:

a. the number of distinct prime factors

b. the number of non-distinct prime factors

c. the number of distinct divisors

d. the number of non-distinct divisors

To my understanding, the references in the comment below suggest the following:

a. $\mathcal{O}(\log\log n)$

b. $\mathcal{O}(\log\log n)$

c. $\mathcal{O}(n^{\frac{1}{\log \log n}})$

d. ?

share|cite|improve this question
so are my suggested answers correct now? – eyaler Jul 9 '12 at 12:12
Perhaps you could add an answer with the details or some indication of how you have found these answers. – lhf Jul 9 '12 at 12:14
There are about $x/\log x$ primes up to $x$, and their product is about $e^x$. Letting $n$ be that product, the number of prime factors is thus about $\log n/\log\log n$, which is not $O(\log\log n)$. – Gerry Myerson Jul 9 '12 at 12:33
Maybe I'm missing something, but I don't see how a number can have "non-distinct divisors"... – J. M. Jul 9 '12 at 12:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.