0

我在学校有这个作业；我们将在 java 中编写一个简单的程序/方法/算法，让我们接受两个数字输入并输出两个输入之间范围内的所有数字的计数，这些输入可以被 2 或 3 或 5 整除。

分配相当简单，因为您可以遍历范围内的所有数字并在满足所有条件时递增计数器。

但是我们也得到了 10 个测试输入和一个评估我们算法效率的计时器。前八个失败，因为八个值 < 10 ^ 6。但是最后两个测试输入值 < 10^18 并且我的算法失败了。

于是我开始思考素数计数函数的方向并筛出埃拉托色尼，但我的头开始疼。关于更快但仍然足够简单的算法的任何想法？

4

1 回答 1

4

我想出了类似的东西

public static void main(String[] args) {
    long a = 123456789012345678L, b = 876543210987654321L;
    long score = getCount(b) - getCount(a - 1);
    System.out.println("Divisible by 2 or 3 or 5: " + score);
}

public static long getCount(long end) {
    return (end / 2) + (end / 3) + (end / 5) - ((end / 6)  + (end / 10) + (end / 15)) + (end / 30);
}

解决方案：

  • 它分别计算有多少个数可以被 2 或 3 或 5 整除并将其相加。
  • 现在我们需要丢弃计数两次的数字：对于 2 和 3，它将是每 6 个数字，对于 2 和 5，每 10 个数字，对于 3 和 5，每 15 个数字
  • 最后，我们需要包含可被 2 和 3 和 5 整除的数字，这些数字在步骤 2 中被丢弃，因此我们每 30 个数字相加。
于 2014-11-07T17:47:10.683 回答