我需要你们的帮助来解决这个具体问题。
区间 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最佳答案
我想出了类似的东西
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 个数字就添加一次。
关于java - 如何在最多 1 秒内找到能被 2、3 或 5 整除的数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26761037/