We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

You only need to compute the square roots of prime numbers, because the square root of a composite number c is the product of the square roots of its prime factors.

E.g. for c=12: sqrt(12) = sqrt(2*2*3) = sqrt(2) * sqrt(2) * sqrt(3)

Actually you don't need a full factorization. Choose any two factors a and b where ab=c: sqrt(12) = sqrt(3) * sqrt(4) (or sqrt(2) * sqrt(12))

You need to be a bit careful, though: a factor can be a perfect square (such as 4), therefore memoize all (!) square roots, even the trivial ones of perfect squares. And even more, you have to increase your precision by a few digits because you'll introduce some rounding errors when multiplying. Adding 15 extra digits is more than enough.

After I added this trick to my code it became about 4x faster for N=100 and P=10000.

## Project Euler #80: Square root digital expansion

You are viewing a single comment's thread. Return to all comments →

You only need to compute the square roots of prime numbers, because the square root of a composite number

cis the product of the square roots of its prime factors.E.g. for

c=12: sqrt(12) = sqrt(2*2*3) = sqrt(2) * sqrt(2) * sqrt(3)Actually you don't need a full factorization. Choose

anytwo factorsaandbwhereab=c: sqrt(12) = sqrt(3) * sqrt(4) (or sqrt(2) * sqrt(12))You need to be a bit careful, though: a factor can be a perfect square (such as 4), therefore memoize all (!) square roots, even the trivial ones of perfect squares. And even more, you have to increase your precision by a few digits because you'll introduce some rounding errors when multiplying. Adding 15 extra digits is more than enough.

After I added this trick to my code it became about 4x faster for N=100 and P=10000.