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.
$\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$.
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.