java数字计数函数

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和5，每15次计数一次
• 最后，我们需要包含可被2、3和5整除的数字，这些数字在第2步中被丢弃，所以我们每30个数字相加一次