For integers $x,y$ where hoth are in range $x,y \in [2,N]$ for an integer Parameter $N$, consider the values the function $z = x^y$ will yield in this ranges. More precisely, given the set
$S = \{ x^y | x \in [2,N], y \in [2,N],N \in \mathbb{N}\}$
how many distinct elements this set has? I try to write codes that will give the answer (what is the cardinality $|S|?$). Doing successive set unions by a loop over the range of $x$ and $y$ is too naive, as it would lead to Computer Memory Overflow.
Instead I tried to use some Basic number-theoretic considerations. I tried to fix one variable, say $x$ and computed a prime factor factorization for it.
$x = p_1^{a_1}p_2^{a_2} \dots p_n^{a_n}$ with prime numbers $p_i$ and $i$ a corresponding index set.
I checked whether all exponents $a_1,a_2,\dots,a_n$ have all a greatest common Divisor other than one; in this case I will have a duplicate in the sequence $z=x^y$, because an Exponent can be factored out and therefore we can find some two different exponents $y$ that can be expressed as a multiple of this greatest common Divisor. However, this Approach gave me wrong results so far(I did some mistakes due to wrong Count of equal elements).
Is there some better way to Count the cardinality even for large $N$ without consuming much computation time and/or memory? Could it be that I have to use hashing techniques? Some people told me that I have to use logarithms, but why?Hints would be greatly appreciated!