Number of Common Factors

🏠 ⬅️ ➡️

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:

  • 1 <= a, b <= 1000
Note: This problem is from LeetCode.
✅ Compiled
✅ Executed
✅ Correct 
program main
    implicit none

    integer :: a, b, n

    a = 12
    b = 6
    print '(I0)', common_factors(a, b)

    a = 25
    b = 30
    print '(I0)', common_factors(a, b)

contains

function common_factors(a, b) result(n)
    implicit none
    integer, intent(in) :: a, b
    integer :: i, n

    n = 0
    do i = 1, min(a, b)
        if (mod(a, i) == 0 .and. mod(b, i) == 0) then
            n = n + 1
        end if
    end do
end function common_factors

end program main
✅ Compiled
✅ Executed
✅ Correct 
module common_factors
    implicit none
    private
    public :: get_common_factors
contains
    function get_common_factors(a, b) result(common_factors)
        integer, intent(in) :: a, b
        integer :: common_factors
        integer :: i

        common_factors = 0
        do i = 1, min(a, b)
            if (mod(a, i) == 0 .and. mod(b, i) == 0) then
                common_factors = common_factors + 1
            end if
        end do
    end function get_common_factors
end module common_factors

program test_common_factors
    use common_factors
    implicit none
    integer :: a, b, common_factors

    a = 12
    b = 6
    common_factors = get_common_factors(a, b)
    write (*,*) "Common factors of", a, "and", b, "are", common_factors

    a = 25
    b = 30
    common_factors = get_common_factors(a, b)
    write (*,*) "Common factors of", a, "and", b, "are", common_factors
end program test_common_factors
🌐 Data from online sources 
def common_factors(a: int, b: int) -> int:
    from math import gcd

    g = gcd(a, b)
    count = 0
    for i in range(1, int(g**0.5) + 1):
        if g % i == 0:
            count += 1
            if i * i != g:
                count += 1
    return count
  1. First, we calculate the greatest common divisor (GCD) of the input integers a and b using the Euclidean algorithm.
  2. Next, we initialize a count variable to store the number of common factors.
  3. Then, we iterate through the numbers from 1 to the square root of the GCD.
  4. For each number i that is a factor of the GCD, we increment the count.
  5. If the square of i is not equal to the GCD, we increment the count again because there is another factor, which is gcd // i.
  6. Finally, we return the count.
🌐 Data from online sources 
int commonFactors(int a, int b) {
    int gcd = std::__gcd(a, b); 
    int count = 0;
    for (int i = 1; i * i <= gcd; i++) {
        if (gcd % i == 0) {
            count++;
            if (i * i != gcd)
                count++;
        }
    }
    return count;
}
  1. First, we calculate the greatest common divisor (GCD) of the input integers a and b using the Euclidean algorithm.
  2. Next, we initialize a count variable to store the number of common factors.
  3. Then, we iterate through the numbers from 1 to the square root of the GCD.
  4. For each number i that is a factor of the GCD, we increment the count.
  5. If the square of i is not equal to the GCD, we increment the count again because there is another factor, which is gcd // i.
  6. Finally, we return the count.