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

C中的编译时LCM/GCD

在C语言中,可以使用以下方法计算两个整数的最大公约数(GCD)和最小公倍数(LCM)

  1. 最大公约数(GCD): 最大公约数可以使用辗转相除法(欧几里得算法)来计算。辗转相除法是一种递归算法,当两个整数a和b(假设a > b)的最大公约数为c时,a和b可以表示为:

a = k1 * c b = k2 * c

其中k1和k2为整数。

辗转相除法的步骤如下:

  • 如果b等于0,则最大公约数为a。
  • 否则,从a中减去b得到新的a(或者直接计算a除以b的余数),然后使用新的a和b重复步骤1。

以下是C语言实现的计算最大公约数的函数:

代码语言:javascript
复制
#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main() {
    int num1 = 56;
    int num2 = 98;
    printf("GCD of %d and %d is: %d\n", num1, num2, gcd(num1, num2));
    return 0;
}
  1. 最小公倍数(LCM): 最小公倍数可以通过以下公式计算:

LCM(a, b) = (a * b) / GCD(a, b)

以下是C语言实现的计算最小公倍数的函数:

代码语言:javascript
复制
#include <stdio.h>

int gcd(int a, int b);
int lcm(int a, int b);

int main() {
    int num1 = 56;
    int num2 = 98;
    printf("LCM of %d and %d is: %d\n", num1, num2, lcm(num1, num2));
    return 0;
}

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

最大公约数几种写法

两个整数最大公约数主要有两种寻找方法: * 两数各分解质因子,然后取出同样有的项乘起来 * 辗转相除法(扩展版) 和最小公倍数(lcm关系:gcd(a, b)×lcm(a, b)...两个整数最大公因子和最小公倍数存在分配律: * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) * lcm(a, gcd(b, c)) = gcd...(lcm(a, b), lcm(a, c)) 在坐标里,将点(0, 0)和(a, b)连起来,通过整数坐标的点数目(除了(0, 0)一点之外)就是gcd(a, b)。...对于gcd(a,b),它是a和b线性组合最小正元素,gcd(b,a%b) 是b与a%b一个线性组合,而a%b是a与b一个线性组合,因而gcd(b,a%b)是一个a与b线性组合,因为a,b都能被...// #include "stdafx.h" int gcd(int a ,int b) { int c = 0; if (a < b) { c = a ;a = b; b= c;//把大元素放在前面

46920
  • 小小GCDLCM拿下拿下

    GCDLCM是算法当中基础之基础,分别对应最大公约数、最小公倍数,在算法竞赛涉及到概率也是比较高GCDLCM在小学时就涉及到了求法,本篇将给大家详解GCDLCM这两个函数,并且提供最简单模板...最大公约数(GCD) 也称为最大公因数或最大公因子,是指两个或多个整数共有的约数中最大一个。在数学,这是指能够同时被这些整数整除最大正整数。...不过,第一种写法在n为0直接返回结果,避免了一次递归调用,可能会有微小性能优势。但在实际应用,这种差异通常可以忽略不计,大家觉得哪个好记就记哪个就行。...例如:8和12最小公倍数为24,24%8=0且24%12=0,只要满足8*a=12*b=c,只要我们得到c是最小即可。...,我们再去用m与n最大公约数与得到公倍数做除法,即:m*n/gcd(m,n),这样便可以得到最小公倍数(LCM),在实现此公式,为了避免m*n会爆int,我们通常会先让一个数m/gcd(m,n),

    5010

    2023-05-17:一个正整数如果能被 a 或 b 整除,那么它是神奇。 给定三个整数 n , a , b ,返回第 n 个神奇数字。 因为答案可能很大,

    3.对于每个二分查找猜测值,计算在 a和b中出现神奇数字个数:m/a + m/b。然后计算 a 和 b 公共倍数 lcm 在 m 范围内出现神奇数字个数:m/lcm。...4.如果出现神奇数字总数大于或等于 n,则将当前猜测值存储在变量 ans ,并将右边界向左移动一位(即缩小区间范围)。...在这个算法,使用了二分查找来搜索第 n 个神奇数字。在最坏情况下,二分查找迭代次数为 O(logN)。因此,时间复杂度为 O(logN)。...go完整代码如下:package mainfunc nthMagicalNumber(n int, a int, b int) int {// 求a和b最小公倍数lcm := int64(a / gcd...("{}", result);}图片c语言完整代码如下:#include long long gcd(long long a, long long b) { return b =

    37000

    Python解决求最大公约数和最小公倍数问题

    一.思路分析 因为之前接触过这个问题,所以自己是知道欧几里得算法和穷举法计算最大公约数,在求出两个数最大公约数之后,便可以利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数最小公倍数...gcd(ka, kb) = k * gcd(a, b),也就是最大公约数运算和倍乘运算可以交换,特殊,当k=2,说明两个偶数最大公约数比如能被2整除。...gcd(ka,kb)=k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换。特殊地,当k=2,说明两个偶数最大公约数必然能被2整除。...当k与b互为质数,gcd(ka,b)=gcd(a,b),也就是约掉两个数只有其中一个含有的因子不影响最大公约数。...,利用lcm(a,b) = (a*b)/gcd(a,b) 计算出两个数最小公倍数: # 求两个数最小公倍数 def lcm(a,b): return a * b / third_way(a,

    1.2K41

    Codeforces Round #813 (Div. 2)(A~C)

    ---- 思想 对于子序列和最小,应遵循最小排列 即判断原序列,前 k 个元素,有多少满足 a_i\le k,满足该条件则不需要交换,否则需要交换 ---- 代码 #include <bits/stdc...Woeful Permutation ---- 题目大意 Origional Link 给定元素为 1\sim n 数组 a 求使得 lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i...,a_i) 最大子序列 ---- 思想 已知 lcm(a,b) = \frac{a\times b}{gcd(a,b)} 若使得 lcm(a,b) 最大,则应尽可能使得 gcd(a,b) = 1 对于序列元素...a_i=i 则有 gcd(i,a_i + 1) = 1 故 ai = i +1, a{i + 1} = i ,满足题意 即: n 为偶数,遵循排列:2,1,4,3,6,5,\dots ,n,n-...,建议自己remake C 一开始思路很乱,后来发现模拟就好了,写完直接交一发就过,没什么算法难度 手速场狂 \color{red}{WA}两道 A,B nt题我真是没救了,前几场着实给我打破防了,这回还好最后没放弃

    24940

    Python数学计算工具5、Python求最最小公倍数

    整数a,b最小公倍数记为[a,b],同样,a,b,c最小公倍数记为[a,b,c],多个整数最小公倍数也有同样记号。 与最小公倍数相对应概念是最大公约数,a,b最大公约数记为(a,b)。...关于最小公倍数与最大公约数,我们有这样定理:(a,b)x[a,b]=ab(a,b均为整数)。 最小公倍数在通分时候会使用到,上文百度解析可以看到a与b之间最小公倍数关系。...''' if y == 0: return x return gcd(y, x % y) def lcm(x, y): ''' 计算最大公倍数...:param x: :param y: :return: ''' return x * y / gcd(x, y) print(lcm(6, 9)) 确定一下刚才结果...:param y: :return: ''' if y == 0: return x return gcd(y, x % y) def lcm(x,

    53710

    Codeforces Round #813 (Div. 2)(A~C)

    ---- 思想 对于子序列和最小,应遵循最小排列 即判断原序列,前 k 个元素,有多少满足 a_i\le k,满足该条件则不需要交换,否则需要交换 ---- 代码 #include <bits/stdc...Woeful Permutation ---- 题目大意 Origional Link 给定元素为 1\sim n 数组 a 求使得 lcm(1,a_1)+lcm(2,a_2)+\dots lcm(i...,a_i) 最大子序列 ---- 思想 已知 lcm(a,b) = \frac{a\times b}{gcd(a,b)} 若使得 lcm(a,b) 最大,则应尽可能使得 gcd(a,b) = 1 对于序列元素...a_i=i 则有 gcd(i,a_i + 1) = 1 故 ai = i +1, a{i + 1} = i ,满足题意 即: n 为偶数,遵循排列:2,1,4,3,6,5,\dots ,n,n-...,建议自己remake C 一开始思路很乱,后来发现模拟就好了,写完直接交一发就过,没什么算法难度 手速场狂 \color{red}{WA}两道 A,B nt题我真是没救了,前几场着实给我打破防了,这回还好最后没放弃

    20910

    C++23新特性—if consteval 编译优化

    一、来龙去脉 C++诞生之日起使用const关键字声明一个常量,随后在C++ 11版本又引入了constexpr 关键字,主要功能是声明一个编译时常量表达式(constant expression)...在C++ 17版本又对该关键字功能进行了扩充,提供了if constexpr表达式,是指在编译阶段可以可以进行条件编译,并根据结果选择可以编译或者不编译哪些代码块。...C++ 20,标准委员会又引入了两个关键字consteval and constinit。...和与const 关键字类似却更加严格,它严格要求变量必须通过编译常量表达式初始化,并且只能被初始化一次。 if consteval也经常用如下表示consteval if。...使用过程需要注意是consteval if语句内部条件表达式必须是在编译时期可计算常量表达式。如果条件表达式在编译时期无法确定,将导致编译错误。

    57120
    领券