News for hackers. Stuff that matters.
Re:Project Euler 001 the Hard Way by kevinventullo on Sunday February 02, 2020 @12:27PM (#22218035)
The inclusion-exclusion algorithm can be made more efficient by observing that you can stop as soon as the lcm's of your subsets exceed N. That should happen fairly early on assuming e.g. N << 2^M.
Re:Project Euler 001 the Hard Way by chupasaurus on Sunday February 02, 2020 @06:45PM (#22220290)
> you can stop as soon as the lcm's of your subsets exceed N

Actually if N < 2 * lcm, because you can't use the fact that the distribution of multiples is the same on (1, lcm) and (k * lcm+1, lcm(k+1)) while you still have to count on (N - N mod lcm + 1, N).