A problem involving squared numbers and can it be solved in polynomial time?

Question

$f(x)$ = $x$ ∈ $S$, $x$ = $x$^$2$

All elements in $S$ must be integers ($1$, $N$) as in counting from $1$ to $N$.

$N$ = $4$

$S$ = $[1,2,3,4]$

Then all elements in $S$ will be squared.

$S$ = $[1, 4, 9, 16]$

I need to be able to have all elements in $S$ to not be a factor of another. (excluding itself if it is alone and $1$)

[4] and [16] are a problem.

• I need to have $S$ to have a length of given $N$.

• I must find a list of $N$ integers that are all $n$^$2$ without any of them sharing factors.

Algorithm

while S hasfactors:

   # re-create list S starting (1, N) until 
   # N integers are found that are not factors of each other

   square all elements in S
   remove = set(factors in S)
     S = set(S) - set(remove)
      if length(S) = N and hasNOfactors:
        OUTPUT {1, 169, 121, 49}

Question

The algorithm runs fine on practical inputs. But, as the magnitude of $N$ gets larger it gets ridiculously slow.

Can this problem be solved in polynomial time?

Answer 1

A simple approach is to use the first $N$ prime numbers plus $1$ if you would like. That is the set of numbers with smallest maximum magnitude that are pairwise relatively prime. You can find them with a sieve, which I believe is about $N^2$, and is certainly polynomial. Having found them, square them and you are done.

If $N=6$ and you start with $1$, the list becomes $1,2,3,5,7,11$, which square to $1,4,9,25,49,121$