2020-09-22：已知兩個數的最大公約數和最小公倍數，并且這兩個數不能是最大公約數和最小公倍數本身。如何判斷這兩個數是否存在？

福哥答案2020-09-22：#福大大架構師每日一題#

1.如果最小公倍數不能被最大公約數整除，不存在這兩個數。

2.求【商】=【最小公倍數/最大公約數】。

3.判斷【商】是否是質數，如果是，直接傳回false。這個步驟可以不要。

4.幂次方縮小【商】範圍，如果【商】是a的b次方，【商】變成a。

5.判斷【商】是否是質數，如果是，直接傳回false。

6.經過所有考驗，傳回true。

代碼用python語言編寫。代碼如下：

# -*-coding:utf-8-*-

import math


# 求快速幂。ret = a^b%p。
def quick_power(a, b, p):
    """
    求快速幂。ret = a^b%p。

    Args:
        a: 底數。大于等于0并且是整數。
        b: 指數。大于等于0并且是整數。
        p: 模數。大于0并且是整數。

    Returns:
        傳回結果。

    Raises:
        IOError: 無錯誤。
    """
    a = a % p
    ans = 1
    while b != 0:
        if b & 1:
            ans = (ans * a) % p
        b >>= 1
        a = (a * a) % p
    return ans


# 求num的exp開方,exp是指數，num是結果。求底數。
def _get_sqrt_range(num, right, exp=2):
    """
        求num的exp開方,exp是指數，num是結果。求底數。
        Args:
            num: 大于等于0并且是整數。
            right: 大于等于0并且是整數。右邊界。
            exp: 大于等于0并且是整數。
        Returns:
            傳回元組，表示一個開方範圍。
        Raises:
            IOError: 無錯誤。
    """
    left = 1
    if num == 0:
        return 0, 0
    if num == 1:
        return 1, 1
    if num == 2 or num == 3:
        return 1, 2
    while True:
        mid = (left + right) // 2
        if mid ** exp > num:
            right = mid
            if left ** exp == num:
                return left, left
            if left + 1 == right:
                return left, right
        elif mid ** exp < num:
            left = mid
            if right ** exp == num:
                return right, right
            if left + 1 == right:
                return left, right
            if mid == 1:
                return 1, 2
        else:
            return mid, mid


# 求對數範圍
def get_log_range(num, basenum):
    """
        求對數範圍。

        Args:
            num: 數，大于等于1并且是整數。
            basenum: 底數，大于等于2并且是整數。

        Returns:
            傳回結果。對數範圍。

        Raises:
            IOError: 無錯誤。
    """
    if num == 1:
        return 0, 0
    else:
        n = 0
        ism = 0
        while num >= basenum:
            if ism == 0 and num % basenum != 0:
                ism = 1
            n += 1
            num //= basenum
        return n, n + ism


# 判斷幂次方，并且傳回底數
def is_power2(num):
    """
        判斷n是否是一個數的幂次方形式。
        Args:
            num: 大于等于0并且是整數。
        Returns:
            傳回結果。true是幂數
        Raises:
            IOError: 無錯誤。
    """
    if num <= 3:
        return False, 0
    else:
        log_range = get_log_range(num, 2)
        if log_range[0] == log_range[1]:
            return True, 2
        expmax = log_range[0]
        expmin = 2
        exp = expmin
        sqrt = 0
        right = 2 ** (1 + log_range[0] // 2)
        while exp <= expmax:
            sqrt = _get_sqrt_range(num, right, exp)
            right = sqrt[0]  # 縮小右邊界範圍
            if sqrt[0] == sqrt[1]:
                return True, sqrt[0]
            if sqrt == (1, 2):
                return False, 0
            exp += 1
        return False, 0


# 米勒-拉賓素性檢驗是一種機率算法，但是，Jim Sinclair發現了一組數：2, 325, 9375, 28178, 450775, 9780504, 1795265022。用它們做 [公式] ， [公式] 以内不會出錯，我們使用這組數，就不用擔心運氣太差了。
def is_prime_miller_rabin(num):
    """
        判斷是否是素數。米勒拉賓素性檢驗是一種機率算法 可能會把合數誤判為質數。

        Args:
            num: 大于等于2并且是整數。

        Returns:
            傳回結果。true為素數；false是非素數。

        Raises:
            IOError: 無錯誤。
    """
    # num=(2^s)*t
    a = 2  # 2, 325, 9375, 28178, 450775, 9780504, 1795265022
    s = 0
    t = num - 1
    num_1 = t
    if num == 2:
        return True
    if not (num % 2):
        return False
    while not (t & 1):
        t >>= 1
        s += 1
    k = quick_power(a, t, num)
    if k == 1:
        return True
    j = 0
    while j < s:
        if k == num_1:
            return True
        j += 1
        k = k * k % num
    return False


# 綜合法
def is_prime_comprehensive(num):
    """
        判斷是否是素數。綜合算法:試除法+米勒拉賓素性檢驗 可能會把合數誤判為質數。

        Args:
            num: 大于等于2并且是整數。

        Returns:
            傳回結果。true為素數；false是非素數。

        Raises:
            IOError: 無錯誤。
    """
    if num <= 1:
        return False
    if num == 2:
        return True
    if num & 1 == 0:
        return False

    # 100以内的質數表
    primeList = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

    # 質數表是否能整除
    for prime in primeList:
        if num == prime:
            return True
        if num % prime:
            if prime * prime >= num:
                return True
        else:
            return False

    # 米勒拉賓素性檢驗
    return is_prime_miller_rabin(num)


# 已知兩個數的最大公約數和最小公倍數，并且這兩個數不能是最大公約數和最小公倍數本身。如何判斷這兩個數是否存在？
def is_exist_two_nums_by_gcd_lcm_not(gcd, lcm):
    """
        已知兩個數的最大公約數和最小公倍數，并且這兩個數不能是最大公約數和最小公倍數本身。如何判斷這兩個數是否存在？
        Args:
            gcd: 大于等于1并且是整數。最大公約數。
            lcm: 大于等于1并且是整數。最小公倍數。
        Returns:
            傳回True，說明存在。
        Raises:
            IOError: 無錯誤。
    """
    # 1.如果最小公倍數不能被最大公約數整除，不存在這兩個數。
    if lcm % gcd != 0:
        return False

    # 2.求【商】=【最小公倍數/最大公約數】。
    quotient = lcm // gcd

    # 3.判斷【商】是否是質數，如果是，直接傳回false。這個步驟可以不要。
    if is_prime_comprehensive(quotient):
        return False

    # 4.幂次方縮小【商】範圍，如果【商】是a的b次方，【商】變成a。
    isloop = True
    quotienttemp = 0
    while isloop:
        isloop, quotienttemp = is_power2(quotient)
        if isloop:
            quotient = quotienttemp

    # 5.判斷【商】是否是質數，如果是，直接傳回false。
    if is_prime_comprehensive(quotient):
        return False

    # 6.經過所有考驗，傳回true。
    return True


if __name__ == "__main__":
    gcd = 5
    lcm = 35
    print("gcd = ", gcd, ",lcm = ", lcm, ",", is_exist_two_nums_by_gcd_lcm_not(gcd, lcm))
    gcd = 5
    lcm = 20
    print("gcd = ", gcd, ",lcm = ", lcm, ",", is_exist_two_nums_by_gcd_lcm_not(gcd, lcm))
    gcd = 3
    lcm = 60
    print("gcd = ", gcd, ",lcm = ", lcm, ",", is_exist_two_nums_by_gcd_lcm_not(gcd, lcm))
           

代碼結果執行如下：

評論