2
4

3 回答 3

3

There is an iterative process to find a squareroot:

def approximate_sqrt(number, depth, start_val):
    for i in range(depth):
        start_val=(start_val+number/start_val)/2
    return start_val

The better the initial guess (start_val), the faster it converges to a reasonable solution.

If start_val>sqrt(number) 

then every iterative value>sqrt(number)

and so it provides an upper bound (similarly for start_val < sqrt(number)). You can reduce the iteration depth to 1 or 2 if your initial guess is pretty close. So for iteratively guessing an upper bound for prime number candidates for example you can call

sqrt_appr=approximate_sqrt(i, 1, sqrt_appr+1)

for the next prime number candidate with the previous estimation for the square root of sqrt_appr and get upper bounds with an error of about 10E-6. (Although every time I checked how close the approximation was, which was for intervals of 3 million numbers, I set sqrt_appr=sqrt(number)+1 to reset the process.)

于 2020-12-05T15:58:59.117 回答
2

Replace the i with i*i:

 if (n % 2 == 0)
    return 2;
for (int i = 3; i * i <= n; i += 2)
    if (n % i == 0)
        return i;
return n
于 2017-03-11T10:02:25.340 回答
2
于 2017-03-11T17:29:00.257 回答