精华内容
下载资源
问答
  • 题目:输入两个正整数m和n,求其最大公约数和最小公倍数。辗转相除法:S1:用m%n得到余数r;S2:更新被除数和除数,m = n, n = r;S3:判断余数r是否为0,r==0,结束循环,负责转向S1;最小公倍数 * 最大公约数 = m * ...

    题目:输入两个正整数m和n,求其最大公约数和最小公倍数。

    辗转相除法:

    S1:用m%n得到余数r;

    S2:更新被除数和除数,m = n, n = r;

    S3:判断余数r是否为0,r==0,结束循环,负责转向S1;

    最小公倍数 * 最大公约数 = m * n

    INPUT m,n
    DO
    r = m MOD n
    m = n
    n = r
    LOOP UNTIL r=0
    PRINTF m
    END

    代码:

    #include 
    展开全文
  • 2020-09-22:已知两个数的最大公约数和最小公倍数,并且这两个数不能是最大公约数和最小公倍数本身。如何判断这两个数是否存在?福哥答案2020-09-22:#福大大架构师每日一题#1.如果最小公倍数不能被最大公约数整除,...

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

    代码结果执行如下:

    ab5f5595a0802dfc9f97450a0699f771.png

    ***

    [评论](https://user.qzone.qq.com/3182319461/blog/1600735568)

    展开全文
  • 输入a,b求出最大公约数和最小公倍数 解法:先求最大公约数 1.判断a,b最大最小值 2.a和b分别和两数的最小值相除,如果值都为0,即,两数的最小值为最大公约数,如果两数不为0,就将最小值减1设为z,然后a和b再...

    输入a,b求出最大公约数和最小公倍数

    解法:先求最大公约数

    1.判断a,b最大最小值

    2.a和b分别和两数的最小值相除,如果值都为0,即,两数的最小值为最大公约数,如果两数不为0,就将最小值减1设为z,然后a和b再分别和z相除

    最小公倍数=a*b/最大公约数

    package main;
    
    //import com.sun.swing.internal.plaf.metal.resources.metal;
    
    public class Main {
    	
    	public static void main(String[] args) {
    		
    		java.util.Scanner in = new java.util.Scanner(System.in);
    		int a = in.nextInt();
    		int b = in.nextInt();
    		//取出a,b的最大最小值
    		int max = a >= b ? a : b;
    		int min = a <=b ? a : b;
    		int maxyue = 0;
    		int minbei2=0;
    		//求最大公约数
    		for(;min>=1;min--) {
    			if(a%min==0 && b%min ==0) {
    				maxyue = min;
    				break;
    			}
    		}
    		//最小公倍数公式法
    		int minbei = a*b/maxyue;	
    		//最小公倍数不是公式法
    		for(int i = max; i<= (a*b); i++) {
    			if(i%a ==0 && i%b == 0) {
    				minbei2 = i;
    				break;
    			}
    		}
    		System.out.println("最大公约数为:"+maxyue);
    		System.out.println("公式法求解最小公倍数为:"+minbei);
    		System.out.println("非公式法求解最小公倍数为:"+minbei2);
    		
    		
    		
    	}
    
    }
    

    展开全文
  • 题目:输入两个正整数m和n,求其最大公约数和最小公倍数。辗转相除法:S1:用m%n得到余数r;S2:更新被除数和除数,m = n, n = r;S3:判断余数r是否为0,r==0,结束循环,负责转向S1;最小公倍数 * 最大公约数 = m * ...

    题目:输入两个正整数m和n,求其最大公约数和最小公倍数。

    辗转相除法:

    S1:用m%n得到余数r;

    S2:更新被除数和除数,m = n, n = r;

    S3:判断余数r是否为0,r==0,结束循环,负责转向S1;

    最小公倍数 * 最大公约数 = m * n

    INPUT m,n
    DO
    r = m MOD n
    m = n
    n = r
    LOOP UNTIL r=0
    PRINTF m
    END

    代码:

    #include <stdio.h>
    
    int main(int argc, const char* argv[]) {
    
    	int m,n,r;
    	scanf_s("%d %d", &m,&n);
    	int a = m, b = n;
    
    	while (1)
    	{
    		r = m % n;
    		m = n;
    		n = r;
    		if (r == 0)
    			break;
    	}
    	printf("最大公约数:%dn",m);
    	printf("最小公倍数:%dn", a * b / m);
    	return 0;
    }
    展开全文
  • 任意给出两个数,求出它的最大公约数和最小公倍数 判断条件: 最小公倍数 = (num1 * num2) / 最大公约数 代码块: #1.接收两个数字 num1 = int(input('Num1: ')) num2 = int(input('Num2: ')) #2.找出两个数中...
  • 从键盘输入两个正整数 a 和 b,求其最大公约数和最小公倍数。 利用格式输入语句将输入的两个数分别赋给 a 和 b,然后判断 a 和 b 的关系,如果 a 小于 b,则利用中间变量 t 将其互换。再利用辗转相除法求出最大公...
  • 第九题输入两个正整数 m 和 n ,求其最大公约数和最小公倍数。穷举法:输入两整数m和n(m>=n)。1)令 i=n ;判断(m%i==0 && n%i==0)是否成立2)如果成立则,求出最大公约数 i。2)否则 i--,重复第2步。代码...
  • 1.如果最小公倍数不能被最大公约数整除,不存在这两个数。 2.求【商】=【最小公倍数/最大公约数】。 3.判断【商】是否是质数,如果是,直接返回false。这个步骤可以不要。 4.幂次方缩小【商】范围,如果【商】是a的b...
  • 题目:从键盘输入两个正整数 a 和 b,求其最大公约数和最小公倍数。 算法思想: 利用格式输入语句将输入的两个数分别赋给 a 和 b,然后判断 a 和 b 的关系,如果 a 小于 b,则利用中间变量 t 将其互换。再利用...
  • 三种算法解决两个正整数最大公约数问题,求3个正整数的最大公约数和最小公倍数,具有良好的输入输出,可以判断输入的正确性。 源代码 /* * 题目:求两个正整数的最大公约数和最小公倍数 */ public class ...
  • ①先判断两个数的大小,如果两数相等,则这个数本身就 是就是它的最大公约数。 ②如果不相等,则用大数减去小数,然后用这个较小数与它们相减的结果相比较,如果相等,则这个差就是它们的最大公约数,而如果不相等,...
  • 本次阐述两个正整数的最大公约数和最小公倍数(求最大公约数的方法和求最小公倍数的方法正好相反) 如下: /*最大公约数的步骤:1,比较a,b的大小,找出最小值min  2,a , b 分别对min取模,  3,判断取模的...
  • 递归求最大公约数和最小公倍数 最大公约数(GCD) int gcd(int a, int b) { return a % b ? gcd(b, a % b) : b; } 用辗转相除法求最大公约数,用递归写的代码会比循环简洁一些。 先判断a除以b...
  • 最大公约数和最小公倍数问题 问题描述 输入二个正整数x0,y0(2 条件: 1.P,Q是正整数 2.要求P,Q以x0为最大公约数,以y0为最小公倍数. 试求:满足条件的所有可能的两个正整数的个数. 分析 这题...
  • 这条算法基于一个定理:两个正整数 a b(a 大于 b),它们的最大公约数等于 a 除以 b 的余数 c 较小数 b 之间的最大公约数。 算法计算过程是这样的: 2个数相除,得出余数 如果余数不为0,则拿较小的数与余数...
  • *13-05-10 15:25 最大公约数和最小公倍数的定义要弄清, 编程思路:把两个数中最大的数对最小的数取模运算,  1.判断最大值  2. 如果num1%num2=0,最大公倍数即是小的那个数,最小公倍数...
  • 求两个数的最大公约数和最小公倍数,只要计算出最大公约数可以求得最小公倍数 两个数字a和b,假设最大公约数为m,a=a1*m,b=b1*m,最小公倍数是a1*b1*m=(a*b)/m 算法一 穷举法 按1、2、3...的顺序判断,能同时...
  • Python中用辗转相除法求两个整数的最大公约数和最小公倍数 首先,得到两个已知的正整数m、n,使得m > n(这里可以通过if语句判断m、n的大小,然后用三条语句使得m > n)例如: if m < n: t = n n = m m ...
  •  P,Q 以x0为最大公约数,通过碾转相除法求得到x0,y0为最小公倍数,通过P*Q/x0可以求得y0,根据最大公约数最小公倍数的关系可以得到 P*Q=x0*y0; 所以穷举Pi(i=1,...,y0),通过P,x0,y0,求出Q,判断是否符合...
  • 基本要求: 求N个数的最大公约数和最小公倍数。用C或C++或java或python语言实现程序解决问题。 1.程序风格良好(使用自定义注释模板) 2.提供友好的输入输出,并进行输入数据的正确性验证。 二·题目分析 先算出两个数...
  • 洛谷P1029 最大公约数和最小公倍数问题 题意 给定 x0与y0 求有多少组正整数对(P,Q) 满足 P与Q的最大公约数是x0 最小公倍数是y0首先我们可以发现x0*y0 == P*Q 那么我们知道 x0 与 y0 的乘积 我们就可以在 O(sqrt(n))...
  • } public int gcd(int a,int b){//最大公约数 if(b==0)return a; return gcd(b,a%b); } public int lcm(int a,int b){//最小公倍数 return a*b/gcd(a,b); } } gcd也可用来判断a,b互质,如果互质,则...
  • #辗转相除法:被除数除数的最大公约数等于除数余数的最大公约数; #暴力穷举法:a=min(x,y)---另一种写法:a=x if x<y else y,每次循环a-=1直到x%a==0 and y%a==0 #最小公倍数=x*y//a #真分数的判断:...
  • 先说一说关于最大公约数最小公倍数怎么算的; 两个数A B相除取余C,第二个数B除C取余,直到整除,那么被除数被最小公倍数。(辗转相除法); 最小公倍数:两个数相乘除以最大公约数; 逻辑流程图 按照题意求最大...
  • 在c语言的学习之中,经常会碰到:  计算最大公约数,最小公倍数和素数判断的问题;  在这里由浅入深总结一下: ... 所以求最大公约数和最小公倍数的问题其实是一类问题;  ①.最小公倍数:  方法
  • 1.如果最大公约数或者最小公倍数有小于1的,不存在这两个数。 2.如果最大公约数等于1,存在这两个数。这个步骤可以不要。 3.如果最大公约数大于最小公倍数,不存在这两个数。这个步骤可以不要。 4.如果最小公倍数不...
  • 1.用C求解两个数的最大公约数和最小公倍数。 首先最小公倍数的求解是依赖于最大公约数的,因为 最小公约数 = 两个整数的乘积 / 最大公约数 最大公约数的求解 (1)使用辗转相除法: 假设两个整数x和y: 第一步,...
  • 利用基本的java循环语句,计算输入的两个整数的最大公约数和最小公倍数。首先,输入两个正整数m和n,判断两个数的大小关系,利用for循环,从2循环到两个数间的最小值,计算出最大的数(两个都能整除),即最大公...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 265
精华内容 106
关键字:

判断最大公约数和最小公倍数