C语言实现求解最小公倍数的算法示例

目录
  • 题目描述
  • 问题分析
  • 方法一：穷举法
  • 方法二：定理法

题目描述

求任意两个正整数的最小公倍数

问题分析

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。

.与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。关于最小公倍数与最大公约数，我们有这样的定理：(a,b)x[a,b]=ab(a,b均为整数)。

——百度百科

我们可以通过两个方法求最小公倍数。

第一种是穷举法，列举所以可能的数，直到找到最小的公倍数；第二种是使用最小公倍数与最大公约数的一个定理——两个整数的最小公倍数等于两数之积除以两个数的最大公因数，即(a,b)x[a,b]=ab（(a,b)表示a和b的最大公约数，[a,b]表示a和b的最小公倍数，a，b均为整数）

方法一：穷举法

假设有两个整数num1和num2，这两个整数的最小公倍数一定大于等于它们的最大值，同时小于等于它们的积。

按从小到大的顺序遍历整个范围内的所有整数，第一个公因数即为它们的最小公倍数。

【不考虑负数，求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）】

#include <stdio.h>

/**
 * @brief 获取最小公倍数（穷举法）
 * @param num1 第一个正整数
 * @param num2 第一个正整数
 * @return 返回最小公倍数
 */
int Get_Min_Comm_Multiple(int num1, int num2)
{
    int i = 0, tmp = 0, mul = 0;
    tmp = num1 > num2 ? num1 : num2; //获取最大值
    mul = num1 * num2;   //两数之积
    for(i = tmp; i <= mul; i++)
    {
        //同时为num1和num2的倍数
        if(i % num1 == 0 && i % num2 == 0)
            break;
    }
    return i;
}

int main()
{
    int num1, num2;

    printf("请输入两个正整数\n");
    scanf("%d%d", &num1, &num2);
    printf("它们的最小公倍数为：%d\n",Get_Min_Comm_Multiple(num1, num2));
    return 0;
}

运行结果

方法二：定理法

使用定理求最小公倍数（两个整数的最小公倍数等于两数之积除以两个数的最大公因数），需要先求出两个整数的最大公因数，最大公因数这里采用辗转相除法。（最大公因数的求法可以参考我上一篇文章——第68天：求最大公约数（使用三种方法））

【不考虑负数，求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）】

#include <stdio.h>

/**
 * @brief 获取两个正整数的最大公因数（辗转相除法）
 * @param num1  第一个正整数
 * @param num2  第二个正整数
 * @return      最大公因数
 */
int Get_Max_Comm_Divisor(int num1, int num2)
{
    int remainder = num1 % num2;  //余数

    while(remainder != 0)
    {
        num1 = num2;      //更新被除数
        num2 = remainder; //更新除数
        remainder = num1 % num2; //更新余数
    }
    return num2;  //最后的除数即为最大公因数
}

/**
 * @brief 获取最小公倍数（定理法）
 * @param num1 第一个正整数
 * @param num2 第一个正整数
 * @return 返回最小公倍数
 */
int Get_Min_Comm_Multiple(int num1, int num2)
{
    /* 最小公倍数 = 两数相乘 / 最大公因数 */
    return num1 * num2 / Get_Max_Comm_Divisor(num1, num2);
}

int main()
{
    int num1 = 0, num2 = 0;

    printf("请输入两个正整数\n");
    scanf("%d%d", &num1, &num2);
    printf("它们的最小公倍数为：%d\n", Get_Min_Comm_Multiple(num1, num2));
    return 0;
}

运行结果

如果程序不作处理（不检测输入的数字是否为正数），此时输入负数，也能返回一个公倍数，但不是“最小”公倍数，不过求负数的最小公倍数本就是无意义的（相当于求两个正数的最大公倍数）。

到此这篇关于C语言实现求解最小公倍数的算法示例的文章就介绍到这了,更多相关C语言求解最小公倍数内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C#获取两个数的最大公约数和最小公倍数示例

    最大公约数:指两个或多个整数共有约束中最大的一个. 最小公倍数:如果有一个自然数a能被自然数b整除,则称a为b的倍数,b为a的约数,对于两个整数来说,指该两数共有倍数中最小的一个. 复制代码 代码如下: /// <summary>/// 最大公约数/// </summary>/// <param name="a"></param>/// <param name="b"></param>/// &

  • Python 代码实现列表的最小公倍数

    目录 1. lcm 2. functools.reduce 3. 实际使用 本篇阅读的代码片段来自于30-seconds-of-python(https://github.com/30-seconds...). 1. lcm from functools import reduce from math import gcd def lcm(numbers): return reduce((lambda x, y: int(x * y / gcd(x, y))), numbers) # EXAMP

  • Python基于递归算法求最小公倍数和最大公约数示例

    本文实例讲述了Python基于递归算法求最小公倍数和最大公约数.分享给大家供大家参考,具体如下: # 最小公倍数 def lcm(a, b, c=1): if a * c % b != 0: return lcm(a, b, c+1) else: return a*c test_cases = [(4, 8), (35, 42), (5, 7), (20, 10)] for case in test_cases: print('lcm of {} is {}'.format(*case, lcm

  • 详解C语言求两个数的最大公约数及最小公倍数的方法

    求两个正整数的最大公约数  思路:这是一个很基本的问题,最常见的就是两种方法,辗转相除法和辗转相减法.通式分别为 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0).根据通式写出算法不难,这里就不给出了.这里给出<编程之美>上的算法,主要是为了减少迭代的次数.      对于x和y,如果y = k * y1, x= k * x1,那么f(x, y) = k * f(x1, y1).另外,如果x = p * x1,假设p为素数

  • C++ 实现求最大公约数和最小公倍数

    C++ 实现求最大公约数和最小公倍数 最大公约数 辗转相除法: int maxDivisor(int a, int b) { int c = b; while (a%b != 0) { c = a%b; a = b; b = c; } return c; } 辗转相减法: int maxDivisor(int a, int b) { while (a != b) { if (a>b) a = a - b; else b = b - a; } return a; } 感谢阅读,希望能帮助到大家,谢

  • 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: 最大公约数 "

  • java求最大公约数与最小公倍数的方法示例

    java求最大公约数与最小公倍数的方法示例

    本文实例讲述了java求最大公约数与最小公倍数的方法.分享给大家供大家参考,具体如下: Gongyueshu.java文件: package math; public class Gongyueshu { public static void main(String[] args) { //从控制台输入两个数据 int m = Integer.parseInt(args[0]); int n = Integer.parseInt(args[1]); int y = 1 ; int b = 1;

  • C语言实现求解最小公倍数的算法示例

    C语言实现求解最小公倍数的算法示例

    目录 题目描述 问题分析 方法一:穷举法 方法二:定理法 题目描述 求任意两个正整数的最小公倍数 问题分析 两个或多个整数公有的倍数叫做它们的公倍数,其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数.整数a,b的最小公倍数记为[a,b],同样的,a,b,c的最小公倍数记为[a,b,c],多个整数的最小公倍数也有同样的记号. .与最小公倍数相对应的概念是最大公约数,a,b的最大公约数记为(a,b).关于最小公倍数与最大公约数,我们有这样的定理:(a,b)x[a,b]=ab(a,b均为整数)

  • Python实现的求解最大公约数算法示例

    本文实例讲述了Python实现的求解最大公约数算法.分享给大家供大家参考,具体如下: 使用Python求解两个数的最大公约数的时候用到了前面介绍的分解质因式.其实,我写分解质因式程序的时候就是因为发现在实现最大公约数求解的过程中用到了这个功能. 比较令我开心的是之前学的一点Python集合处理功能居然在这个时候也派上了用场,小程序的完成让人感觉比较舒心. 代码实现如下: #!/usr/bin/python from collections import Counter def PrimeNum(

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • Python实现的求解最小公倍数算法示例

    本文实例讲述了Python实现的求解最小公倍数算法.分享给大家供大家参考,具体如下: 简单分析了一下,前面介绍的最大公约数的求解方法跟最小公倍数求解方法类似,只需要改一个简单的条件,然后做一点简单的其他计算.问题的解决也是基于分解质因式的程序. 程序实现以及测试case代码如下: #!/usr/bin/python from collections import Counter def PrimeNum(num): r_value =[] for i in range(2,num+1): for

  • C语言编程题杨氏矩阵算法快速上手示例详解

    目录 题目概要 一.解题思路 二.具体代码 题目概要 有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路 对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的 我们来介绍一种方法

  • Python实现简单求解给定整数的质因数算法示例

    本文实例讲述了Python实现简单求解给定整数的质因数算法.分享给大家供大家参考,具体如下: 接着做题遇到求解质因数分解的问题,思想很简单,就是需要遍历从1到该整数本身,并且判断当数字为质数时加入列表最后输出即可,求解这样的一个正整数的质因数分解,关键在于理解,每次得到一个质因数之后需要更新整数为:原始整数除以这个质因数的值,循环直至原始整数的值小于2终止,输出结果即可,实现如下: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒

  • Python&Matlab实现蚂蚁群算法求解最短路径问题的示例

    Python&Matlab实现蚂蚁群算法求解最短路径问题的示例

    目录 1知识点 1.1 蚁群算法步骤 1.2 蚁群算法程序 2蚂蚁算法求解最短路径问题——Python实现 2.1源码实现 2.2 ACA_TSP实现 3 蚂蚁算法求解最短路径问题——Matlab实现 3.1流程图 3.2代码实现 3.3结果 1 知识点 详细知识点见:智能优化算法—蚁群算法(Python实现) 我们这一节知识点只讲蚁群算法求解最短路径步骤及流程. 1.1 蚁群算法步骤 设蚂蚁的数量为m,地点的数量为n,地点i与地点j之间相距Dij,t时刻地点i与地点j连接的路径上的信息素浓度为

  • GO语言中常见的排序算法使用示例

    目录 快排 冒泡 选择排序 插入排序 希尔排序 二分法查找 快排 package main import ( "fmt" "math/rand" "time" ) func main() { li:=[]int{1,3,5,2,4,6,9,7} left:=0 right:=len(li)-1 fmt.Println(quick_sort(li,left,right)) } func quick_sort(li []int, left,right

  • Java实现求子数组和的最大值算法示例

    Java实现求子数组和的最大值算法示例

    本文实例讲述了Java实现求子数组和的最大值算法.分享给大家供大家参考,具体如下: 一般C和C++在算法实现中使用较多,下面我们通过java语言实现算法,更有亲切感. 题目: 输入一个整形数组,数组里有正数也有负数. 数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和. 求所有子数组的和的最大值. 例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2, 因此输出为该子数组的和18. 实现代码: package arrDe

  • Python实现的寻找前5个默尼森数算法示例

    本文实例讲述了Python实现的寻找前5个默尼森数算法.分享给大家供大家参考,具体如下: 找前5个默尼森数. 若P是素数且M也是素数,并且满足等式M=2**P-1,则称M为默尼森数.例如,P=5,M=2**P-1=31,5和31都是素数,因此31是默尼森数. python2代码如下: from math import sqrt def isPrime(n): 'judge whether a positive integer is a prime number!' if n==1: return

随机推荐