java - 如何在最多 1 秒内找到能被 2、3 或 5 整除的数字

Question

我需要你们的帮助来解决这个具体问题。

区间 a <= b [1, 10^18] 中有多少个数字可以被 2、3 或 5 整除？

结果必须在最多 1 秒内运行!

标准程序将使用如下所示的 for 循环。

a = 1;
b = 1000000000
results = 0;

for (int i = a; i <= b; i++){
    if (i % 2 == 0 || i % 3 == 0, i % 5 == 0){
        results++;
    }
}
System.out.println(results);

但是如果我输入很大的数字，我的程序需要很多时间才能给出结果。

示例 1:

a = 11，b = 30，结果 = 14

示例 2:

a = 123456789012345678，b = 876543210987654321，结果 = 552263376115226339

Answer 1

我想出了类似的东西

public static void main(String[] args) {
    long a = 123456789012345678L, b = 876543210987654321L;

    long start = System.currentTimeMillis();

    long score = getCount(b) - getCount(a - 1);

    System.out.println("Time: " + ((System.currentTimeMillis() - start)));
    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 个数字就添加一次。