Knowing that the perfect squares are located at well-defined intervals:
- Q 1 = 0 + 1 = 1
- Q 2 = 1 + 3 = 4
- Q 3 = 4 + 5 = 9
- Q 4 = 9 + 7 = 16
- Q 5 = 16 + 9 = 25
Simplifying:
- Q 1 = 1
Q n = Q n-1 + 2n-1
We can print the sequence, without relying on sqrt
, which makes it the fastest way (just do not ... is not always like this ) to process such a sequence:
function QuadradoPerfeito(n) {
var out = '';
var x = 1;
for (var i = 3; ; i += 2)
for (var j = 0; j < i; j++) {
if (x > n) return out;
out += x + (j == 0 ? ' QUADRADO PERFEITO' : '') + '<br>';
x++;
}
}
document.body.innerHTML = QuadradoPerfeito(100);
But two nested loops ... is not it slower?
Despite having two nested loops, the total amount of calculations made is linear, because the output condition is over the x
variable, which is incremented by each pass.
In addition, the browser is able to optimize such nested loops in such a way,
that even redoing the code with a single loop, the result is still slower,
however it is much easier to understand logic.
Here's a simulation of what happens when calling the method with n=20
:
i=3:
j=0: x=1 // QUADRADO PERFEITO
j=1: x=2
j=2: x=3
i=5:
j=0: x=4 // QUADRADO PERFEITO
j=1: x=5
j=2: x=6
j=3: x=7
j=4: x=8
i=7:
j=0; x=9 // QUADRADO PERFEITO
j=1; x=10
j=2; x=11
j=3; x=12
j=4; x=13
j=5; x=14
j=6; x=15
i=9:
j=0; x=16 // QUADRADO PERFEITO
j=1; x=17
j=2; x=18
j=3; x=19
j=4; x=20
Version with a single loop, provided by @Bacco
Based on the comments on how many loops, @Bacco has made a version that has exactly the same logic, but in a loop only.
But be aware: this unique tie is not better in terms of performance than the double ties shown at the beginning of this answer! This version is intended to help less experienced people visualize logic.
function QuadradoPerfeito(n) {
var out = '';
var x = 1;
var s = 1;
var i;
for ( i = 1; i <= n ; i++ ) {
out += i;
if ( i == x ) {
out += ' QUADRADO PERFEITO';
x = i + (s += 2 );
}
out += ' <br>';
}
return out;
}
document.body.innerHTML = QuadradoPerfeito(100);