Every natural number greater than 1 is divisible by a prime number

Sorry if this question has been asked, but a couldn't find one using the method I need.

I want to prove that every natural number greater than 1 is divisible by some prime number using the WOP. I have done this by taking S to be the set of natural numbers greater than 1 which aren't divisible by a prime. But my notes now say to do it by taking S to be the set of all factors of n which are greater than 1.

Any help would be appreciated. Thanks.

• $S$ is not empty ($n \in S$), so it has a smallest element, let's call it $p$. Now argue that $p$ is a prime. – Daniel Fischer Dec 12 '13 at 13:09

Take $S$ to be the set of non-$1$ factors of $n$. By the WOP, there is a smallest one, say $n_0$. Then $n_0$ has no divisors except for $1$ and $n_0$ itself, because any divisor of $n_0$ would be a divisor of $n$.
So, $n_0$ is a...