Java语言中10,000以下的数字是3、5或7的倍数之和

Question

我知道如何让程序将3、5和7的倍数之和加起来，但我不确定如何让程序只使用每个数字一次。例如，我可以让程序找出所有的数字，并将它们相加为3，然后对5执行相同的操作，但数字15将出现在最后的数字中两次。我不确定我怎么才能让它只取一次号码。谢谢你的帮助。

Answer 1

最简单的方法是使用for循环，如下所示：

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

Answer 2

虽然生成并测试方法很容易理解，但如果您想在较大的数字上运行此方法，则效率也不是很高。相反，我们可以使用inclusion-exclusion principle。

这个想法是首先通过分别查看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 (参见triangle number)。

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

现在我们只需要使用inclusion exclusion来获得最终的和：

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

这将更好地扩展到更大的n，而不仅仅是循环所有的值，但要注意溢出并在必要时更改为BigInteger。

Answer 3

使用Set存储唯一的倍数，然后对集合的值求和。