Re:Project Euler
by philiplu on Tuesday October 15, 2024 @01:59AM
(#41845383)
That's exactly what Project Euler problems often do, especially once you get past the first hundred or two. Problems are scaled so a brute-force often means hours to days of compute time, or worse.
You get to recognize the effect - if I see a problem that's clearly number-theory related and with a limit of 10^12, I know they're looking for a sublinear algorithm, probably O(n^(2/3)) thanks to various multiplicative function ideas that appear over and over.
You get to recognize the effect - if I see a problem that's clearly number-theory related and with a limit of 10^12, I know they're looking for a sublinear algorithm, probably O(n^(2/3)) thanks to various multiplicative function ideas that appear over and over.