Java Program to Compute the Number of Integers Divisible By k in the Range [a..b]

这是Google、Amazon、TCS、Accenture等顶级IT公司面试中经常出现的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来计算可被给定值整除的整数的数量。我们还将为之创建 Java 程序。这是一种在数论和程序员竞赛中经常使用的非常有效的方法。

问题陈述

存在三个 整数 a、b 和 k，它们满足上述条件给出的约束。

[a,b] 范围内的数字，其中 [a,b] 在 1 到 1000 之间（包含上限），是可以被 k 整除的数字。例如，如果

a=5, b=15, and k=3

在此范围内可被 k=3 整除的整数是 6、9、12 和 15。因此，答案是 4。

问题解决方案

暴力解法

其中第一个是暴力方法，包括遍历范围内的每个整数。

然后尝试确定它是否是 k 的倍数。如果是，则增加计数器。

输出

 
4   

更好的方法

另一种更快的技术利用了一个事实，即发现给定范围内可被 k 整除的数字等于算术序列的总和。无需检查每个数字；因此，可以找到第一个和最后一个可整除的数字，然后计算此序列中的项数。

输出

 
4   

最优数学解法

最佳解法可以用直接数学公式来描述。换句话说，以下工作解释了可被 k 整除的总整数数，直到 n，等于 floor(n/k)。利用这个性质，可以在范围 [a,b] 内计算可被 k 整除的整数数量，方法如下

输出

 
4   

结论

如何计算范围内可被特定数字 k 整除的数位数量是一个基本问题，属于简单问题类别，但这些问题在数论的几乎每个领域以及 竞争性编程 的大多数问题中都要求掌握。有多种方法可以解决此问题。在这里，我们有各种可以用来解决此问题的方法

暴力解法： 遍历范围内的每个数字，然后确定要考虑的数字是否可被 k 整除。这种方法很简单，但计算量非常大，尤其是当需要计算 n 的大值时，会花费大量时间。

更好的方法： 通过应用算术规则找到范围内的第一个和最后一个可整除的数字，然后找到第一个提到的序列的项数。这比用于解决该问题的试错法要好得多。

最优数学解法： 通过应用整数除法，使用直接公式来方便地计算可整除整数的数量。与早期方法相比，它更快，更适合使用，尤其是对于大范围。