公因子的数目
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 15.9 MB
/*
* 思路:
* 使用 Java Stream API 进行简化。
* 可以使用 IntStream 来生成从 1 到 min(a, b) 的范围,
* 然后过滤出能同时整除 a 和 b 的整数,
* 最后计数这些整数的数量即可。
*/
import java.util.stream.IntStream;
public class CommonFactorsStream {
public static int commonFactors(int a, int b) {
int min = Math.min(a, b);
return (int) IntStream.rangeClosed(1, min)
.filter(i -> a % i == 0 && b % i == 0)
.count();
}
public static void main(String[] args) {
System.out.println(commonFactors(12, 6)); // 输出: 4
System.out.println(commonFactors(25, 30)); // 输出: 2
}
}
解释
方法:
该题解采用了暴力法来找到两个数a和b的所有公因子。首先,它遍历了所有从1到min(a, b)(含)的整数,因为任何大于a和b中的较小值的数不可能是它们的公因子。对于每一个这样的整数i,检查i是否同时是a和b的因子,即a和b都能被i整除。如果是,计数器ans增加1。遍历完成后,ans中的值就是a和b的公因子的总数。
时间复杂度:
O(min(a, b))
空间复杂度:
O(1)
代码细节讲解
🦆
在算法中,为何选择遍历到min(a, b)而不是max(a, b),能否详细解释这样选择的原因?
▷🦆
算法中使用了暴力法,是否存在更高效的算法来解决这个问题,例如基于最大公约数的方法?
▷🦆
在算法实现中,ans变量用于计数公因子,这种计数方式是否有可能在某些情况下导致重复计数?
▷🦆
在实际代码实现过程中,是否考虑了输入的异常情况,例如a或b为非常小或非常大的边界值?
▷