# Prove that there are infinitely many natural numbers that are not powers of any prime.

I am wondering whether there is a way to prove that the set consisting of all natural numbers that are not powers of any prime is infinite. For example, 6 is such a natural number. Just to make this clear, what I mean is that any numbers that are powers of 2,3,5,7... (prime numbers) are not in the defined set. So 2,4,8 ; 3,9,27 are not in the set.

For a set to be infinite, I mean the following:

I am trying to this by proving that this set is equivalent to $\Bbb N$ but it is really hard to find an explicit bijection. Another way to do this is that I can prove the set consisting of all natural numbers that are powers of a primes is countably infinite. But it seems that the complement of a countably infinite set in $\Bbb N$ may not be countably infinite?

Can someone please give me a hand? Thanks.

• $p q$, for $p$ and $q$ distinct primes? – Andreas Caranti Mar 6 '17 at 11:07
• If $n$ is odd, $n >1$, can $2n$ be a power of a prime? – quasi Mar 6 '17 at 11:07
• What do you mean by giving a hand??? – sgrmshrsm7 Mar 6 '17 at 11:08
• @Sagar Mishra: The phrase "give me a hand" is an idiom. It means "help me" (e.g., "help me up"). – quasi Mar 6 '17 at 11:10
• p*(p+1) for any prime? – Eric Duminil Mar 6 '17 at 12:56
