Description#
Given two positive integers a and b, return the number of common factors of a and b.
An integer x is a common factor of a and b if x divides both a and b.
Example 1:
Input: a = 12, b = 6
Output: 4
Explanation: The common factors of 12 and 6 are 1, 2, 3, 6.
Example 2:
Input: a = 25, b = 30
Output: 2
Explanation: The common factors of 25 and 30 are 1, 5.
Constraints:
Solutions#
Solution 1: Enumeration#
We can first calculate the greatest common divisor $g$ of $a$ and $b$, then enumerate each number in $[1,..g]$, check whether it is a factor of $g$, if it is, then increment the answer by one.
The time complexity is $O(\min(a, b))$, and the space complexity is $O(1)$.
1
2
3
4
| class Solution:
def commonFactors(self, a: int, b: int) -> int:
g = gcd(a, b)
return sum(g % x == 0 for x in range(1, g + 1))
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int commonFactors(int a, int b) {
int g = gcd(a, b);
int ans = 0;
for (int x = 1; x <= g; ++x) {
if (g % x == 0) {
++ans;
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
| class Solution {
public:
int commonFactors(int a, int b) {
int g = gcd(a, b);
int ans = 0;
for (int x = 1; x <= g; ++x) {
ans += g % x == 0;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func commonFactors(a int, b int) (ans int) {
g := gcd(a, b)
for x := 1; x <= g; x++ {
if g%x == 0 {
ans++
}
}
return
}
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function commonFactors(a: number, b: number): number {
const g = gcd(a, b);
let ans = 0;
for (let x = 1; x <= g; ++x) {
if (g % x === 0) {
++ans;
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
|
Solution 2: Optimized Enumeration#
Similar to Solution 1, we can first calculate the greatest common divisor $g$ of $a$ and $b$, then enumerate all factors of the greatest common divisor $g$, and accumulate the answer.
The time complexity is $O(\sqrt{\min(a, b)})$, and the space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
| class Solution:
def commonFactors(self, a: int, b: int) -> int:
g = gcd(a, b)
ans, x = 0, 1
while x * x <= g:
if g % x == 0:
ans += 1
ans += x * x < g
x += 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public int commonFactors(int a, int b) {
int g = gcd(a, b);
int ans = 0;
for (int x = 1; x * x <= g; ++x) {
if (g % x == 0) {
++ans;
if (x * x < g) {
++ans;
}
}
}
return ans;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| class Solution {
public:
int commonFactors(int a, int b) {
int g = gcd(a, b);
int ans = 0;
for (int x = 1; x * x <= g; ++x) {
if (g % x == 0) {
ans++;
ans += x * x < g;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| func commonFactors(a int, b int) (ans int) {
g := gcd(a, b)
for x := 1; x*x <= g; x++ {
if g%x == 0 {
ans++
if x*x < g {
ans++
}
}
}
return
}
func gcd(a int, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| function commonFactors(a: number, b: number): number {
const g = gcd(a, b);
let ans = 0;
for (let x = 1; x * x <= g; ++x) {
if (g % x === 0) {
++ans;
if (x * x < g) {
++ans;
}
}
}
return ans;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}
|
