查找 N 的最大因子，使得 NF 小于 K（Java）

给定两个数字 N 和 K，我们的任务是确定最小的 X 值，使得 N < X*K。

示例 1

输入

int num = 8

int K = 7

输出

N 的最大因子是 2。

解释

对于给定的数字，小于 K 且能被 N 整除的数字是 1、2 和 4。因此，X 的最小值为 2，使得 8 < 2*7 = 14。因此，N 的最大因子是 2。

示例 2

输入

int num = 999999733,

int K = 999999732

输出

N 的最大因子是 999999733。

解释

由于整数 999999733 是一个素数，它可以被 1 和它本身整除；因为 K 小于 999999733。由于 999999733 < 999999733*999999732，可以确定 999999733 是 X 的最小值。因此，N 的最大因子是 999999733。

方法：朴素方法

可以使用方程 K * X = N 来表示给定的问题表达式。该方程的主要目标是减小 X。因此，我们必须确定能整除 N 的最大 K。

算法

步骤 1: 初始化变量 k 和 num。

步骤 2: 重复遍历 [1, K]。

步骤 3: 声明用于保存所需响应的临时变量。

步骤 4: 验证 (n % i) = 0 是否对于每个整数 i 都成立。

步骤 4.1: 继续更新 max 变量，该变量跟踪到 i 为止遍历过的 N 的最大除数。

步骤 5: Num/maxi，必须返回该值，是所需的答案。

实施

文件名: LargestFactorofN.java

输出

The largest factor of N is 2

复杂度分析

上述代码的时间复杂度为 O(K)，空间复杂度为 O(1)。

方法：高效方法

此方法通过迭代到数字平方根的因子，有效地确定给定数字 num 的最大因子，该因子小于或等于设定的阈值 K。它通过使用基本的数学特性来实现这一点。

算法

步骤 1: 创建一个函数来确定小于或等于 K 值的最大数字因子。

步骤 2: 创建一个名为 res 的变量来保存结果；它应初始化为 0。

步骤 3: 重复步骤 1 到步骤 j，直到 num 的平方根。

步骤 4: 它通过确定 num 对 j 取模是否等于 0，来确定 j 是否是 num 的因子。

步骤 5: 如果 j 是一个因子，它会将 j 与 K 进行比较。如果 j 小于或等于 K，它会将 res 更新为当前值和 j 中的最大值。

步骤 6: 它还确定 num 除以 j 是否等于或小于 K。如果是这种情况，则表示 num/j 是一个小于或等于 K 的因子，在这种情况下，res 将按需更新。

步骤 7: 最后，函数返回小于或等于 K 的最大因子 (res)。

实施

文件名: EfficientLargestFactorN.java

输出

复杂度分析

其中“N”代表输入数字，上述代码的时间复杂度为 O(sqrt(N))，空间复杂度为 O(1)。