最大公约数和最小公倍数

喜欢吃鱼的青年 2020-10-15 16:55:03 ⋅ 392 阅读

一. 基本概念:

  1. 如果数a能被数b整除,a就叫做b的倍数,b就叫做a的约数。约数和倍数都表示两个整数的关系,不能单独存在。
    几个整数中公有的约束,叫做这几个数的公约数;其中最大的一个,叫做这几个数的最大公约数。数学公式记为(12,16) = 4

  2. "倍"与"倍数"是不同的概念,"倍"表示两个数相除的商,他可以是整数、小数或者分数。"倍数"只是在数的整除的范围内,相对于"约数"而言的一个概念,表示的是能被某一个自然数整除的数。 几个自然数公有的倍数,叫做这几个数的公倍数,其中最小的一个自然数,叫做这几个数的最小公倍数[12,15,18]=180. 若干个互质数的最小公倍数为他们的乘积

  3. 质数:又称素数.一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数,叫做质数;否则叫做合数

二. 求法

一. 辗转相除法

1.推理篇

求(319,377)的最大公约数

∵ 319÷377=0(余319)
∴(319,377)=(377,319);

∵ 377÷319=1(余58)
∴(377,319)=(319,58);

∵ 319÷58=5(余29)
∴ (319,58)=(58,29);

∵ 58÷29=2(余0)
∴ (58,29)= 29;
∴ (319,377)=29。

2.代码实现

#pragma mark - 最大公约数:辗转相除法
- (NSInteger)getTheMaxMethod:(NSInteger)a b:(NSInteger)b {
    NSInteger result = 0;
    
    while (a%b != 0) {
        result = a % b;
        a = b;
        b = result;
    }
    return b;
}


NSInteger maxValue = [self getTheMaxMethod:377 b:319];
NSLog(@"%zd", maxValue);  //输出为29


//两个数的最小公倍数等于两个数相乘除以最大公约数
NSInteger minMutableValue = [self getTheMaxMethod:377 b:319];
NSLog(@"%zd", maxValue);  //输出为4147

3.扩展

1.求多个数的最大公约数,可以先求出其中任意两个数的最大公约数,再求这个最大公约数与第三个数的最大公约数,依次求下去,直到最后一个数为止。
最后所得的那个最大公约数,就是所有这些数的最大公约数。

2.求多个数的最小公倍数时,可以先求出其中两个数的最小公倍数,再求这两个数的最小公倍数与第三个数的最小公倍数,以此类推,直到最后一个数为止。
最后得到的最小公倍数就是这几个数的最小公倍数。
二. 更相相减法

1.推理篇

求260和104的最大公约数
260-104 = 156;
156-104 = 52;
104-52 = 52
52-52 = 0;

2.代码篇

#pragma mark - 最大公约数:辗转相减法
- (NSInteger)getTheMaxMethod2:(NSInteger)a b:(NSInteger)b {
    while (a!= b) {
        if (a > b) {
            a = a-b;
        } else {
            b = b - a;
        }
    }
    return a;
}

NSInteger maxValue = [self getTheMaxMethod2:260 b:104];
NSLog(@"%zd", maxValue);  //输出为52

三.递归求解
#pragma mark - 最大公约数:递归法
- (NSInteger)getTheMaxMethod3:(NSInteger)a b:(NSInteger)b  {
    
    NSInteger temp;
    if (a < b) {
        temp = a;
        a = b;
        b = temp;
    }
    
    if (a%b == 0) {
        return b;
    } else {
        return [self getTheMaxMethod3:a b:a%b];
    }
}
四.质因数分解法
把每个数`分别`分解质因数,再把各数中`全部` `公有`质因数相乘,所得的积 就是这几个数的最大公约数

例如:求24和60的最大公约数。
24 = 2x2x2x3;
60 = 2x2x3x5;
公有质因数相乘 2x2x3 = 12, 所以(24,60) = 12;

#pragma mark -分解单个质因数
- (NSArray *)fenjieZhiYinShuActionWithNumber:(NSInteger)passNumber {
    NSMutableArray *tempArr = [NSMutableArray array];
    int n = (int)passNumber;
    for(int k = 2; k <= n; ){     //k从第一个素数开始
        if(n%k == 0){             //如果k是n的因数
             [tempArr addObject:@(k)];
            n /= k;               //此时n变为n/k,继续循环查找n的质因数
        }
        else
            k++;                  //如果此时k不是n的因数,将k值加1
    }
   
    return tempArr;
}


#pragma mark - 筛选公有质因数
- (NSArray *)getThePublicZhiYinShuArr1:(NSArray *)arr1  arr2:(NSArray *)arr2 {
   
    NSMutableArray *tempIndexArr = [NSMutableArray array]; //下标数组
    NSMutableArray *elementArr = [NSMutableArray array]; //元素数组
    NSInteger lastRecord = 0;
    for (int i=0; i < arr1.count; i++) {
        NSNumber *currentNumber = arr1[I];
        //动态计算下标, 重点在动态  因为假如有多个indexOfObject: 始终只返回第一个的下标  removeObject:则会删除所有相同元素
        NSUInteger index = [arr2 indexOfObject:currentNumber inRange:NSMakeRange(lastRecord, arr2.count-lastRecord)];
        
        if (index != NSNotFound) {
            if ([tempIndexArr containsObject:@(index)] == NO) {
                [tempIndexArr addObject:@(index)];
                [elementArr addObject:arr2[index]];
                lastRecord++;
            }
        }
    }
    return elementArr;
}

#pragma mark - 使用
    NSArray *arr1 = [self fenjieZhiYinShuActionWithNumber:8]; //2x4
    NSArray *arr2 = [self fenjieZhiYinShuActionWithNumber:30]; //2x15
    
    NSArray *allPublicArr = [self getThePublicZhiYinShuArr1:arr1 arr2:arr2];  //2
    NSInteger allCount = 1;
    for (int i = 0; i < allPublicArr.count; i++) {
        allCount = allCount * [allPublicArr[i] integerValue];
    }


参考文章1:最大公约数
参考文章2:百度百科
参考文章3:分解质因数

 

全部评论: 0

    我有话说:

    Chrome 87 发布,获多年来性能提升

    Chrome 87 正式版现已发布。谷歌方面表示,由于进行了许多底层改进,本月的更新代表了多年来 Chrome 性能的提升。 此版本包含的一些更新内容有: 现在,Chrome 会优先

    微信程序抖音实战-视频弹幕

    如果你去抖音只是为了看视频就少了一乐趣,评论区才是有趣的地方,边看视频边看评论的弹幕是不是更有意思

    SQLite 3.34.0 发布,世界上使用量的数据库引擎

    为数众多的其它应用中,是世界上使用量的数据库引擎...

    精品推荐:一览GitHub上受程序欢迎的5Java开源项目

    列举了GitHub上一些流行的Java项目。从Mockitos到Guava,以及 java-design-patterns等供大家学习。

    社交电商「礼物说」完成亿元C1轮融资;蚂蚁金服估值$1600亿全球独角兽;智能健身舱「公园盒子」获数千万A+轮融资;

    「礼物说」完成亿元C1轮融资,用礼物红包程序发力社交电商;蚂蚁金服成为全球独角兽公司,估值1600亿美元;24H智能健身舱「公园盒子」获数千万A+轮融资;

    2017 年度编程语言榜,Java 流行、JavaScript 没价值?

    2017 年度编程语言榜,Java 流行、JavaScript 没价值?

    SQLite 3.35.3 发布,常用的数据库引擎

    为数众多的其它应用中,是世界上使用量的数据库引擎...

    微信程序营销之转盘(二)

    第一个版本的转盘都是用图片做的,奖品等信息都是不无法修改的,说白了就是没啥实际用途,作者我就直接用canvas撸了一个全手工绘制的转盘分享给大家

    程序实战-幸运转盘

    微信程序幸运转盘

    精品推荐:【CKEditor】全球优秀的网页在线文字编辑器之一

    CKEditor是新一代的FCKeditor,是一个重新开发的版本。CKEditor是全球优秀的网页在线文字编辑器之一,因其惊人的性能与可扩展性而广泛的被运用于各网站。

    全网详细的一篇SpringCloud总结

    什么是Spring cloud 构建分布式系统不需要复杂容易出错。Spring Cloud 为常见的分布式系统模式提供了一种简单且易于接受的编程模型,帮助开发人员构建有弹性的、可靠的、协调的

    连续三年蝉联第一,Flink 荣膺全球活跃的 Apache 开源项目(附课程)

    2020年,一个注定会被历史铭记的一年。在全球化合作受到挑战的环境下,作为全球的开源软件基金会,Apache 软件基金所引领的开源社区,依然汇聚了全球的顶尖开发人员,交出了一份鼓舞人心的成绩单

    家再获B轮30亿融资加入滴滴造车梦/程序的危机!程序受到联合挑战!/“数据杀熟”涉欺诈......

    家再获B轮30亿融资加入滴滴造车梦;程序的危机!程序受到联合挑战!;“数据杀熟”涉欺诈,住宿、出行、购票要当心;5千万用户信息遭泄露,或将面临2万亿美刀处罚,Facebook是否还能坚挺?

    微信程序 - iconfont 图标字体

    你还在使用图片作为程序的图标?猪告诉大家如何在程序上使用iconfont字体图标

    微信程序-Image的widthFix属性rpm尺寸的使用

    在做微信程序的商品详情页,商品的详情是图片集合,渲染完成后发现图片加载的很不自然

    「开源中国」公布 2019 年度受欢迎中国开源软件,一个.NET都没

    经过 22 天的投票评选,今天 2019 年度受欢迎中国开源软件产生了。

    VUE 开源库收藏版(一):史上全面的学习资源 ,附GitHub源码地址

    VUE 开源库收藏版(一):史上全面的学习资源 ,附GitHub源码地址

    GitHub精选:2018年11月份热门的Java开源项目

    又到了揭晓 11 月份热门 Java 开源项目排名的时候了,在本月的名单中,出现了几个新面孔,如Java 核心知识库、轻量级容错组件Resilience4j .....

    世界之烂的开发项目:苦撑12年,600多万行代码…

    “ 你见过烂的项目,撑了多长时间才完蛋?六个月?一年?今天介绍的这个奇葩项目,不但一开始就烂得透透的,还硬...