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. 
 A: $\newcommand{\Set}[1]{\left\{ #1 \right\}}$$\newcommand{\N}{\mathbb{N}}$Is there any reason why you would want an explicit bijection?
Because you can prove that your set 
$$
X = \Set{ x \in \N : \text{$x$ is not a power of a prime}}
$$ 
is in a bijection with the natural numbers without making the bijection explicit.
First note that
$$
n \mapsto 2 \cdot (2 n + 3)
$$
is an injective map from $\N$ to your set $X$. (I have taken $2 n + 3$ so that it works whether one includes zero in $\N$ ot not.)
Then $x \mapsto x$ is an injective map $X \mapsto \N$.
This guarantees that there is a bijection $\N \to X$.
A: From your example, you can get $6^1$, $6^2$, etc. Thus you can set up a one-to-one correspondence $\Bbb N\to\{6^{n+1}:n\in\Bbb N\}:n\mapsto 6^{n+1}$.
A: If i understand your question correctly, your set is defined as :
$S = n \in \mathbb N | n \ne p^q$ for any prime $p$ and positive integers $q$
It is sufficient to prove that a subset of $S$ is infinite.
Consider the subset $P = n!, n \in \mathbb N, n\ge 3$ clearly, it satisfies your condition that they are not the powers of a single prime.
Now suppose we have a set $T = [1,2,....,n]$ such that $P(T) = n$ for some natural n. ($P(T)$ denotes the cardinality of set $ T$). For there to exist a bijection $f: P \to T, P(T) = P(P)$. But clearly, $(n+4)! \in P$. Which means that the cardinality of $P$ is at least $(n+4) -3 =n+1$. Thus there cannot exist any bijection,for any natural $n$. Thus, $P$ is an infinite set. Since, $P \subset S$, $S$ is also infinite.
I just made the proof up right now. If there are anu fatal errors,please point it out. I will remove/edit the answer likewise.
