How to list all powerful numbers below N in $O(\sqrt{N})$time?

[castrate]

Powerful numbers: A positive integer n is powerful if $p^2$ is a divisor of n for every prime factor p in n.
From OEIS we know that the number of powerful numbers below N is about $2.1732\sqrt{N}=O(\sqrt{N})$

In fact I do have an algorithm to do so, but some technical issue beats me.
The outline of the algorithm is as follows:

powerful←[1]
primelist←primes below $\sqrt{n}$
for p in primelist:
for powerful_num in powerful:
newpowerful_list←[powerful_num*$p^2$,powerful_num*$p^3$,powerful_num*$p^4$......]
powerful←sorted(powerful+newpowerful_list)//this step costs too much

The marked step aims to keep the order of the powerful number list, but both sorting and binary searching/inserting(which needs to move many numbers in the list) are too time-consuming. This algorithm counts every powerful number only once, for which I think myself on the right track, but due to that step, the algorithm would not be capable for $N>10^{11}$(in fact computing time seems to grow linearly for $N>10^{8}$).

So, how could I optimize my algorithm? Any help is appreciated.

[pjt33]

You don't want to do multiple sorts. What I would try is to use the characterisation that powerful numbers have a canonical representation $a^2 b^3$ where $b$ is squarefree. Calculate the squarefree numbers up to $\sqrt[3]{n}$ and then put these $b$s in a priority queue. For each $b$ the numbers generated by increasing $a$ go in ascending order, so the main loop is to pop a $b$, emit its current value, increment its $a$, and reinsert if below $n$. Time will be within a logarithmic factor of the number of powerful numbers emitted.