# What can be the maximum and minimum number of prime factors?

A number is having exactly $72$ factors or $72$ composite factors. what can be the maximum and minimum number of prime factors of this number? I search on internet and I found a solution of that question, solution like:

factorise $72$ as $2\times2\times2\times3\times3$ so total no of maximum prime factors is $5$ and minimum is $1$.

But I could not understand why is this and what is the correct way to find maximum and minimum prime factors from total no of factors or total composite factors. So please help me out. Thanks in advance.

First, note that the positive integer $n = p_1^{\alpha_1} \cdots p_n^{\alpha_n}$ has

$$\prod_{k=1}^n (\alpha_k + 1) = (\alpha_1 + 1) \cdot (\alpha_2 +1 ) \cdots (\alpha_k + 1)$$

factors.

So if your number $n$ has 72 positive divisors, then

$$72 = (\alpha_1 + 1) \cdot (\alpha_2 +1 ) \cdots (\alpha_k + 1)$$

where $k$ is the number of distinct primes in the prime factorization for $n$. You correctly noted that $72 = 2\cdot 2\cdot 2\cdot 3\cdot 3$. To get as many prime factors as possible, set $k = 5$ and $\alpha_1 = \alpha_2 = \alpha_3 = 1$ and $\alpha_4 = \alpha_5 = 2$. So for example your $n$ could be equal to $2^2 3^2 5^2 7^1 11^1$. Check that this has $72$ factors. For the minimum, just set $k=1$ and $\alpha_1 = 71$. So for example your $n$ could be $2^{71}$.

If you're just looking at composite factors, the process is similar. Since $n$ has $\prod_{k=1}^n (\alpha_k + 1)$ total factors, $k$ prime factors and $1$ (which is not composite) as factor, the number of composite factors is

$$\left( \prod_{k=1}^n (\alpha_k + 1)\right) - (k+1).$$

The minimum is still $1$ (set $\alpha_1 = 73$). For the maximum, you might need to do some casework. You want the number $72 + k + 1$ to have exactly $k$ prime factors. So $k$ cannot get too large. (See below for precise reasoning.) I tried the first $10$ values of $k$ and $k = 2$ (yielding $\prod_{k=1}^n (\alpha_k + 1) = 75$) was the only match. So the maximum number of prime factors for the case when you only want composite factors is $2$. An example number would be $2^{24} 3^2$. Check that this has $75$ total factors, three of which ($1$, $2$, $3$) are not composite.

Here is why $k$ cannot get too large in the composite case. Let $\{ p_1, \cdots, p_k, \cdots \}$ be the set of primes in order. So $p_1 = 2$, etc. Let the smallest number with exactly $k$ prime factors be $S_k = p_1 \cdots p_k$. So $S_1, S_2, S_3, S_4 = 2,6,30,210$. Note that $S_k \geq 2^k$.

We want $72 + k+1$ to have exactly $k$ prime factors, which means $72 + k + 1 \geq S_k$. But this means $72 + k + 1 \geq 2^k$, which is false for all $k \geq 7$. (Polynomials grow more slowly than exponentials.) So we can stop our search in the composite case for all $k \geq 7$.

For any $k$ you can find a number with exactly $k$ factors but only $1$ prime factor, e.g. $2^{k-1}$ has factors $2^0,2^1,...,2^{k-1}$.

In general, if a number $n$ has prime factors $p_1,...,p_r$ you can write it as $p_1^{a_1}\times\cdots\times p_r^{a_r}$, where each $a_i\geq 1$. The factors of this are all the numbers expressible as $p_1^{b_1}\times\cdots\times p_r^{b_r}$, where for each $b_i$ we have $0\leq b_i\leq a_i$. Thus there are $a_i+1$ choices for $b_i$, and $(a_1+1)\times\cdots\times(a_r+1)$ choices overall. So if a number has $r$ prime factors and $k$ factors, we must have $k$ being a product of $r$ numbers, each greater than $1$.

The largest product which gives $k=72$ is $2\times2\times2\times3\times3$, so you can have at most $5$ prime factors (and for exactly $5$, you must have $n=p_1p_2p_3p_4^2p_5^2$ for some primes $p_1,...,p_5$).