In the 80s this was a play around with MSBasic challenge.
"We only need to go up to n/2 because anything larger than that can’t be a divisor of n"
What we learned the hard way in the 80s is mathematically you only need to go up to the sqrt(n) but calculating sqrt(n) in software is so slow compared to n/2, that for the limited numeric range of interpreted basic in the 80s, its faster to check the "excess" numbers between sqrt(n) and n/2. For 16 bit ints figure 15000 or so extra modulus checks was faster than one floating point sqrt().
There's a funny calculus lesson in there, that adding the derivative to the previous sqrt can be kind of useful as you already have an approximation to sqrt(x) from last time around. Just +1 or more to "make sure" your estimated sqrt() increases faster than real sqrt(). Also don't forget if you're only checking odds to increment your sqrt estimate twice.
Programming as a craft never changes, although the problems and associated numbers have varied over the last 40 years or so. Its always been the same people playing the same game.
"We only need to go up to n/2 because anything larger than that can’t be a divisor of n"
What we learned the hard way in the 80s is mathematically you only need to go up to the sqrt(n) but calculating sqrt(n) in software is so slow compared to n/2, that for the limited numeric range of interpreted basic in the 80s, its faster to check the "excess" numbers between sqrt(n) and n/2. For 16 bit ints figure 15000 or so extra modulus checks was faster than one floating point sqrt().
There's a funny calculus lesson in there, that adding the derivative to the previous sqrt can be kind of useful as you already have an approximation to sqrt(x) from last time around. Just +1 or more to "make sure" your estimated sqrt() increases faster than real sqrt(). Also don't forget if you're only checking odds to increment your sqrt estimate twice.
Programming as a craft never changes, although the problems and associated numbers have varied over the last 40 years or so. Its always been the same people playing the same game.