代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你两个正整数 a
和 b
,返回 a
和 b
的 公 因子的数目。
如果 x
可以同时整除 a
和 b
,则认为 x
是 a
和 b
的一个 公因子 。
示例 1:
输入:a = 12, b = 6 输出:4 解释:12 和 6 的公因子是 1、2、3、6 。
示例 2:
输入:a = 25, b = 30 输出:2 解释:25 和 30 的公因子是 1、5 。
提示:
1 <= a, b <= 1000
方法一:枚举
直接枚举 $[1, 1000]$ 中的每个数,判断其是否是 $a$ 和 $b$ 的公因子,如果是,则答案加一。
时间复杂度 $O(n)$。本题中 $n = 1000$。
class Solution:
def commonFactors(self, a: int, b: int) -> int:
return sum(a % i == 0 and b % i == 0 for i in range(1, 1001))
class Solution {
public int commonFactors(int a, int b) {
int ans = 0, n = Math.min(a, b);
for (int i = 1; i <= n; ++i) {
if (a % i == 0 && b % i == 0) {
++ans;
}
}
return ans;
}
}
class Solution {
public:
int commonFactors(int a, int b) {
int ans = 0;
int n = min(a, b);
for (int i = 1; i <= n; ++i) {
if (a % i == 0 && b % i == 0) {
++ans;
}
}
return ans;
}
};
func commonFactors(a int, b int) int {
ans := 0
for i := 1; i <= a && i <= b; i++ {
if a%i == 0 && b%i == 0 {
ans++
}
}
return ans
}
function commonFactors(a: number, b: number): number {
const n = Math.min(a, b);
let ans = 0;
for (let i = 1; i <= n; i++) {
if (a % i == 0 && b % i == 0) ans += 1;
}
return ans;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。