java - 优化代码以获取给定范围内可被整数整除的整数个数

Question

给定范围 x, y。我需要计算介于两者之间且可被 n 整除的所有数字。

我知道最简单的方法是遍历整个范围

for(int i=x;i<=y;i++) if(i%n ==0) counter++; 

计数器保存答案。

但这对于大范围来说工作起来太慢了。例如 x=0 和 y=3,000,000,000。

我确信我可以使用某种关系来减少迭代次数并优化此代码以提高速度。我搜索了但找不到。请任何人帮助我。

非常感谢。

Answer 1

这有效:(e+1 - s) / d + (e%d < (s+d-1)%d) . (它使用 C 语义和整数运算，并假设开始是非负数。s 是开始值，e 是结束值 [包括]，d 是除数。)

更新:更好的解决方案是 e/d - (s-1)/d .这是受 User448810 的启发。这就要求我们要积极；处理零或负 s(或 e)需要调整向零截断(对于这个问题，我们希望向负无穷大)。

负值更新:以下适用于 s 和 e 在其类型范围内的任何值，前提是 s <= e 和 0 < d:

e = e <  0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;

基本上，前两个语句等同于e = e/d和 s = (s-1)/d将除法修改为向 -infinity 而不是向零舍入(以便 -1/10 产生 -1 而不是 0)。