Generate perfect squares divisible by integer n

Question

I am attempting to find an efficient method for generating or finding all perfect squares divisible by a given natural number $n$. My current approach iterates over all squares, returning those found to be divisible by $n$, so anything is an improvement. I don't know if this relevant, but $n$ is known to be 1 more than a prime. Thank you.

Answer 1

One way to do it is to factor $n$ into the form $\prod\limits_{i=1}^s p_i^{a_i}$, then define the number $m$ as $\prod\limits_{i=1}^s p_i^{\lceil a_i/2 \rceil}$. The numbers that you want are precisely the numbers of the form $(am)^2$ where $a$ is a positive integer.