Proper Divisors / Number Theory Let $g(n)$ be the product of the proper positive integer divisors of $n$. (Recall that a proper divisor of $n$ is a divisor other than $n$.) For how many values of $n$ does $n$ not divide $g(n)$, given that $2 \le n \le 50$?
I'm aware of the terminology regarding proper divisors. However, I was not able to crack this problem in under 10 minutes. 
Thought Process  1: Find all primes between 2 and 50. However, this returned the wrong answer. 
Thought Process 2: I thought of brute forcing the answer, but that seemed too long. 
Finally, I ended up getting an answer (which was correct), but I needed a faster way. Does anyone know a way to get the answer (in under 10 minutes)? 
 A: Given a number $2\leq n\leq 50$ with prime decomposition
$$
n = 2^{e_2}\cdot3^{e_3}\cdots47^{e_{47}}
$$
the number of divisors of $n$, including $n$ and $1$, is
$$
\sigma(n) = (1+e_2)(1+e_3)\cdots(1+e_{47})
$$
Note that if there are two or three divisors according to this count, then $n$ is not divisible by the product of its proper divisors, because that product will be $1$ in the case of two divisors, and $\sqrt n$ in the case of three divisors (if there are three divisors, then $n$ is necessarily the square of a prime number, because exactly one of the exponents above is $3$, and the rest are $1$).
Now, on the other hand, if there are four or more divisors, then there is at least one proper divisor that is neither $1$ nor $\sqrt n$. Call that divisor $m$. Both $m$ and $\frac mn$ are proper divisors of $n$, they are distinct, and their product equals $n$. So they both appear as factors of $g(n)$, which means that $g(n)$ is divisible by $n$.
Therefore you are looking for primes and squares of primes.
A: We are looking for integers $n$ between $2$ and $50$, inclusively, such that $g(n)$ does not divide $n$. 
Let’s take a look at a few cases.


*

*Suppose that $n$ is prime. The only proper divisor must be $1$ and so $g(n) = 1$ which means that $n$ cannot divide $g(n)$.

*Suppose that $n$ is the square of a prime. Then there is some prime $p$ such that $n = p^2$ and so $g(n) = p$. Thus, $n$ cannot divide $g(n)$.

*Suppose that $n$ is the product of 2 distinct primes, say $p$ and $q$. Then $g(n) = pq $ and so $n$ divides $g(n)$.
Note: we can generalize this to any number of distinct primes as long as there is more than $1$.

*Suppose that $n$ is the product of the square of a prime and a different prime. Say, $n = p^2q.$ Then $g(n) = p^3q = pn.$
Note: we can generalize from here but I leave that to you.
This means that we need only count primes and prime squares between $2$ and $50$, inclusively.
So, we can quickly count $19$ such integers.
Namely, $\{4, 9, 25, 49\}$ (because counting the prime squares is relatively quick) and $\{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47\}$. Note that for a reasonably small number like $50$, counting primes is somewhat quick since we need only list $2$ then check odd integers, most of which should be known to be prime or composite based on sight to many of us.
The grand total is $19$.
A: If $a$ and $b$ are two different divisors of $n$, then $ab\mid g(n)$, so if $n=ab$ with $1\lt a\lt b\lt n$, then $n\mid g(n)$. Thus the only possible $n$'s that don't divide $g(n)$ are primes and squares of primes. Since $g(p)=1$ and $g(p^2)=p$ when $p$ is prime, we need only count the size of the set $\{2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49\}$. I get $19$.
A: If $n$ is not a prime and not the square of a prime, then it has a proper divisor $d$ such that $n/d$ is $\neq d$ and hence another proper divisor. Hence $n = d \cdot n/d$ divides $g(n)$.
