添加100到4000000之间的所有值,可以除以3或5但不能同时除3和5

Question

添加100到4000000之间的所有值,可以除以3或5但不能同时除3和5

无法弄清楚如何实施该规定的第二部分.这是我到目前为止所拥有的:

var sum = 0;
for (var i = 100; i < 4000001; i++) {
    if (i % 3 || i % 5 === 0) {
        sum = sum + i;
    } 
}

Answer 1

你可以在没有任何循环的情况下计算总和,使用算术级数之和的公式:我们有

    3 + 5 + 6 + 9 + 10 + 12 + 18 + 20 + ...
=   3 + 6 + 9 + 12 + 15 + 18 + ...
  + 5 + 10 + 15 + 20 + ...
  - 2*(15 + 30 + 45 + ...)

请注意,我们将3和5的所有倍数相加,但然后将两倍的倍数减去两倍,因为它们被计算为3和5的倍数的两倍.

设g(n)是从1到n的整数之和.我们有g(n) = n*(n+1)/2.

设f(n)为1和n之间可被3或5整除的整数之和,但不能两者兼而有之.然后我们有

f(n) = 3*g(floor(n / 3)) + 5*g(floor(n/5)) - 30*g(floor(n/15))

并且m和n之间的整数之和可以被3或5整除,但不是两者都可以f(n) - f(m - 1).这可以用O(1)计算.