首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

蓝桥杯 算法训练 最大最小公倍数

问题描述 已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。 输入格式 输入一个正整数N。 输出格式 输出一个整数,表示你找到的最小公倍数。...算法分析 如果 n <= 2, 那么最小公倍数为 n 如果 n 是奇数,那么最小公倍数最大值为末尾的三个数相乘 如果是偶数的话,如果同时出现两个偶数肯定会不能构成最大值了,因为会被除以2分两种情况:...如果 n 是偶数且不是三的倍数, 比如8,那么跳过n-2这个数而选择 8 7 5 能保证不会最小公倍数被除以2所以最小公倍数最大值为n * (n – 1) * (n – 3) 如果 n 是偶数且为三的倍数...,比如6,如果还像上面那样选择的话,6和3相差3会被约去一个3,又不能构成最大值了。...那么最小公倍数最大值为(n – 1) * (n – 2) * (n – 3) C++算法 #include "iostream" #include "algorithm" using namespace

90310
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    算法最大公约数、最小公倍数、数学归纳法

    最大公约数: 如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数。 几个整数中公有的约数,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。...12、16的公约数有1、2、4,其中最大的一个是4,4是12与16的最大公约数,一般记为(12,16)=4。...公约数的用途就是约分: 把一个分数的分子和分母同时除以它们的公约数,分数的值不变,这个过程就叫约分; 约分让这个分数用起来更简单 最小公倍数: 几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个自然数...,叫做这几个数的最小公倍数。...4的倍数有4、8、12……,6的倍数有6、12、18……,4和6的公倍数有12、24,……,其中最小的是12。 一般记为[4,6]=12。

    1.7K80

    最大公约数和最小公倍数

    如何求最大公约数? 在数学中,我们用分解质因数和短除法来求解,如下图,就是百度经验上用短除法求最大公约数和最小公倍数的一个过程。 ? 短除法 那么用程序如何实现呢?...我们可以用另一种方法,叫做辗转相除法,又叫欧几里得算法。 3. 欧几里得算法最大公约数: 我们用(A, B)表示求A(较大的那个数)和B(较小的那个数)的最大公约数。...欧几里得算法的公式如下: 首先让A / B = C ~ D,如果余数D为0,那么B就是最大公约数; 如果D不为0,那么就让除数和余数继续做上面的运算,即B / D = E ~ F,直到余数为0,此时的除数就是最大公约数...二、最小公倍数 求出了最大公约数,求最小公倍数就很简单了,因为存在如下公式: 假如(a, b)的最大公约数是m,那么最小公倍数n = a * b / m。...所以,要求最小公倍数,可以先用上述方法求出最大公约数。

    1.2K50

    详解最大公约数和最小公倍数

    = b) { if (a > b) a = a - b; else b = b - a; } printf("最大公约数%d\n最小公倍数%d", a, (x / a) * (y /...a) * a); return 0; } 也不废话,直接讲思路:很简单将a,b差值赋给a,b中的较小值,直到a,b相等,此时a=b=最大公约数,不过你要想问我为什么,不妨直接看《九章算术》,最大公约数得到后最小公倍数还不好求吗...= 0) { t = a % b; a = b; b = t; } printf("最大公约数%d\n最小公倍数%d", a, (x / a) * (y / a) * a); return...0; } 思路:如果a<b,第一次循环就会直接将a,b交换位置(这也是这个算法精妙所在,完全不用考虑a,b的大小关系),然后往下循环时将a%b赋给较小值b,将b赋值给a,最后得到最大公约数a,但要注意更相损减法后...但综上所述,如果要攻算法,建议用辗转相除,因为更相损减法容易运行超时啦

    9710

    python计算最大公约数和最小公倍数_python怎么求最大公约数和最小公倍数

    python怎么求最大公约数和最小公倍数 一、求最大公约数 用辗转相除法求最大公约数的算法如下: 两个正整数a和b(a>b),它们的最大公约数等于a除以b的余数c和b之间的最大公约数。...比如10和25,25除以10商2余5,那么10和25的最大公约数,等同于10和5的最大公约数。...具体代码如下:def gongyue(a, b): “”” 欧几里得算法—-辗转相除法 :param a: 第一个数 :param b: 第二个数 :return: 最大公约数 “”” # 如果最终余数为...=0): temp = a % b a = b b = temp return a 二、求最小公倍数 求出a,b的最大公约数后,利用gongbei(a,b) = (a*b)/gongyue(a,b) 计算出两个数的最小公倍数...:# 求两个数的最小公倍数 def gongbei(a,b): return a * b / gongyue(a, b) 推荐学习:Python视频教程 发布者:全栈程序员栈长,转载请注明出处:https

    62820
    领券