10,000以下的数字总和,是Java中3,5或7的倍数

Question

我知道如何让程序为3,5和7中的每一个加总多个的总和,但我不确定如何让程序只使用每个数字一次.例如,我可以让程序找出所有数字并将它们加起来为3然后对5进行相同的操作,但是数字15将在最终数字中两次.我不确定我是如何得到它只采取一次数字.谢谢你的帮助.

Answer 1

虽然生成和测试方法很容易理解,但如果你想在更大的数字上运行它也不是很有效.相反,我们可以使用包含 - 排除原则.

我们的想法是首先通过分别查看3,5和7的倍数来总结太多数字.然后我们减去我们计算两次的数,即3*5,3*7和5*7的倍数.但现在我们减去了太多,需要再次加回3*5*7的倍数.

我们首先找到所有整数的总和,1..n它是的倍数k.首先,我们m = n / k通过整数除法找出有多少,四舍五入.现在我们只需要总结序列k + 2*k + 3*k + ... + m*k.我们分解k并获得k * (1 + 2 + ... + m).

这是一个众所周知的算术系列,我们知道它们总和k * m * (m + 1)/2(参见三角形数字).

private long n = 9999;
private long multiples(long k) {
    long m = n / k;
    return k * m * (m + 1) / 2:
}

现在我们只使用包含 - 排除来获得最终总和:

long sum = multiples(3) + multiples(5) + multiples(7)
         - multiples(3*5) - multiples(3*7) - multiples(5*7)
         + multiples(3*5*7);

这将扩展得更好,n而不仅仅是循环遍历所有值,但要注意溢出并BigInteger在必要时更改为s.

Answer 2

最简单的方法是使用for循环:

int sum = 0;
for(int i=1; i<10000; i++)
{
    if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0)
        sum += i;
}