本文分享自微信公众号 - 福大大架构师每日一题（gh_bbe96e5def84）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

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))

代码结果执行如下：

---

评论

2022-09-07：给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如，序列 [4,6,16] 的最大公约数是 2 。 数组的一个

2022-09-07：给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如，序列 [4,6,16] 的最大公约数是 2 。 数组的一个 子序列 本质是一个序列，可以通过删除数组中的某些元素（或者不删除）得到。 例如，[2,5,10] 是 [1,2,1,2,4,1,5,10] 的一个子序列。 计算并返回 nums 的所有 非空 子序列中 不同 最大公约数的 数目 。 输入：nums = [5,15,40,5,6]； 输出：7。

答案2022-09-07：

n/1 + n/2 + n/3 + n/4 + ... + n/n 收敛于 O(N * logN)，N是最大值，当做结论记住。

代码用rust编写。代码如下：

fn main() {
    let mut arr = vec![5, 15, 40, 5, 6];
    let ans = count_different_subsequence_gcds(&mut arr);
    println!("ans = {}", ans);
}

const MIN_VALUE: i32 = -1 << 31;

// n不是数字的个数，是数组中的最大值
// 体系学习班，
// 根据数据量猜解法，
// 要想通过测试，一定要让计算量不超过10的7次方~10的8次方
// n/1 + n/2 + n/3 + n/4 + ... + n/n -> O(N * logN)
fn count_different_subsequence_gcds(nums: &mut Vec<i32>) -> i32 {
    // 找到数组中的最大数！max
    let mut max = MIN_VALUE;
    for num in nums.iter() {
        max = get_max(max, *num);
    }
    // 1~max，哪个数有哪个数没有
    let mut set: Vec<bool> = vec![];
    for _ in 0..max + 1 {
        set.push(false);
    }
    for num in nums.iter() {
        set[*num as usize] = true;
    }
    let mut ans = 0;
    // a是当前想确定，是不是某个子序列的最大公约数，有a！
    let mut a = 1;
    while a <= max {
        // 1)找到，离a最近的，a的倍数！1 2 3 ... g就是
        let mut g = a;
        while g <= max {
            if set[g as usize] {
                break;
            }
            g += a;
        }
        // 2) 找到了a最近的倍数，g
        // g + 0 , g ?= a
        // g + a , g ?= a
        // g + 2a , g ?= a
        // g + 3a , g ?= a
        let mut b = g;
        while b <= max {
            if set[b as usize] {
                g = gcd(g, b);
                if g == a {
                    ans += 1;
                    break;
                }
            }
            b += a;
        }
        a+=1;
    }
    return ans;
}

fn gcd(m: i32, n: i32) -> i32 {
    if n == 0 {
        m
    } else {
        gcd(n, m % n)
    }
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下：

---

左神java代码

2、求m和n的最大公约数与最小公倍数（最大公约数：转辗相除法）

2、求m和n的最大公约数与最小公倍数（最大公约数：转辗相除法）。 public class Jiejue2 { public static void main(String args[]) { System.out.println(gongyue(8, 6)); System.out.println(gongbei(8,6)); } //求m和n的最大公约数 public static int gon

2、求m和n的最大公约数与最小公倍数（最大公约数：转辗相除法）。

public class Jiejue2 {

public static void main(String args[]) {
     System.out.println(gongyue(8, 6));
     System.out.println(gongbei(8,6));
    }
   
    //求m和n的最大公约数
    public static int gongyue(int m, int n) {
     while(m % n != 0) {
      int temp = m % n;
      m = n;
      n = temp;
     }
     return n;
    }
   
    //求m和n的最小公倍数
    public static int gongbei(int m, int n) {
     return m * n / gongyue(m, n);
    }
   
}

今天关于php计算两个整数的最大公约数常用算法小结和php计算两个数的最大公约数和最小公倍数的介绍到此结束，谢谢您的阅读，有关2020-09-22：已知两个数的最大公约数和最小公倍数，并且这两个数不能是最大公约数和最小公倍数本身。如何判断这两个数是否存在、2020-09-22：已知两个数的最大公约数和最小公倍数，并且这两个数不能是最大公约数和最小公倍数本身。如何判断这两个数是否存在？、2022-09-07：给你一个由正整数组成的数组 nums 。 数字序列的 最大公约数 定义为序列中所有整数的共有约数中的最大整数。 例如，序列 [4,6,16] 的最大公约数是 2 。 数组的一个、2、求m和n的最大公约数与最小公倍数（最大公约数：转辗相除法）等更多相关知识的信息可以在本站进行查询。

本文标签：

• php
• 最大公约数
• 最小公倍数
• 整数算法