Is there any shorter and efficient way to find
if a number can be formed by the product of two distinct square numbers
for example
- 36=4*9
- 144=16*9
help me with an algorithm or the logic
Is there any shorter and efficient way to find
if a number can be formed by the product of two distinct square numbers
for example
help me with an algorithm or the logic
You are looking for a number formed by product of two squares, so you have it written in this form: $n = a^2 b^2$, apply product of powers property, so you have: $n = a^2 b^2 = (ab)^2$, so at the end you have to check if this number is a square. If you want to control if the number is made of two factors you have to find its square root, then check if it's a prime number (as in comment $49 = 7\cdot 7$, $7$ is prime, so you will get only $1 \cdot 49$).
So taking your examples: 36 is a square because $36 = 6 \cdot 6 $, now take factors: $6 = 1 \cdot 2 \cdot 3$, so $36 = 1 \cdot 4 \cdot 9 $, at the end you multiply some of them: $36 = 4 \cdot 9$ or $36 = 1 \cdot 36$.
144 is a square because $144 = 12 \cdot 12 $, now take factors: $12 = 1 \cdot 2 \cdot 2 \cdot 3$, so $144 = 1 \cdot 4 \cdot 4 \cdot 9 $, at the end you multiply some of them: $144 = 1 \cdot 144$ or $144 = 4 \cdot 36$ or $144 = 9 \cdot 16$.
If you try with $15$ you can find any product of squars because $15$ isn't a square.
As Blex wrote, a number $n$ is the product of two distinct squares $a^2$ and $b^2$ if and only if can be written as $n = a^2 b^2 = (ab)^2$. Thus, first of all, all such numbers are themselves squares.
Given a square number $n = r^2$, it is the product of two distinct squares if and only if its square root $r$ can be written as the product of two distinct numbers $r = ab$. If we're allowed to choose $a = 1$ and $b = r$ (or vice versa), then this is always possible for any $r > 1$, but I assume you're only interested in the cases where $a$ and $b$ are strictly between $1$ and $r$.
In that case, there are only two ways in which this factorization can fail: either when $r$ is itself a prime, in which case it has no divisors other than $1$ and itself, or when it is the square of a prime $p$, in which case its only non-trivial factorization is $r = p^2$.
Thus, we get the result:
A number $n > 1$ can be written as the product of two distinct squares (both greater than $1$) if and only if it is the square of a number which is neither a prime nor the square of a prime.