数计数函数

Question

我在学校有这样的作业，我们要用java编写一个简单的程序/方法/算法，它让我们接受两个数字输入和输出计数，在两个输入之间的范围内，这些数字可以除以2、3或5。

赋值相当简单，因为只要满足所有条件，就可以迭代范围内的所有数字，并增加计数器。

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

于是我开始思考素数计数函数和筛子埃拉托斯提尼，但是我的头开始受伤了。对一个更快但仍然很简单的算法有什么想法吗？

Answer 1

我想出了这样的东西

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位和每15位数5位。
• 最后，我们需要包含可以被2和3整除的数字，以及在步骤2中被丢弃的数字，所以我们将每30个数字相加。