Let's see the leetcode problem Sum of Square Numbers first.

The first solution often goes by brute force way. Let's write it first.

function judgeSquareSum(c: number): boolean {
    for (let x = 0; x*x <= c; x++) {
        for (let y = 0; y*y <= c; y++) {
            if (x*x + y*y === c) {
                return true;
            }
        }
    }
    return false;
};

How to speed up this process? Well, instead of increasing x and y by 1 in each loop, we can think of it reversely. So we need to calculate x^2 + y^2 = c, then we can convert it into Math.sqrt(c - y^2). Then we can increment y by one, then calculate if the result can be sqrtted.

// x^2 + y^2 = c
// x = Math.sqrt(c - y^2)
function judgeSquareSum(c: number): boolean {
    for (let y = 0; y * y <= c; y++) {
        const x = Math.sqrt(c - y * y);
        if (x === Math.floor(x)) return true;
    }
    return false;
};

OK, now we solved this problem.

This problem is actually very similar to the part of the calculation of Fermat's factorization method. Fermat's factorization method is used to calculate factorization of a number. So given a number n, we need to find a and b with n = a * b.

Follow below process, we can convert n = a * b into other formats:

n = a * b
n = ((a+b)/2)^2 - ((a-b)/2)^2

x = (a+b)/2
y = (a-b)/2

n = x^2 - y^2
n = (x-y) * (x+y)

So we can follow the solution of above problem to calculate x and y in n = x^2 - y^2. Then we can calculate a and b by n = (x-y) * (x+y.

OK, let see the code.

// n = x^2 - y^2
// y = sqrt(x^2 - n)
function factor(n: number): [number, number] {
    if (n % 2 == 0) return [2, n / 2];

    let x = 0;
    while (true) {
        const yy = x * x - n;
        if (yy >= 0) {
            const y = Math.sqrt(yy);
            if (y === Math.floor(y)) {
                return [x - y, x + y];
            }
        }
        x++;
    }
}

console.log(factor(9));