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.
Best Answer
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$.