最大公约数和最小公倍数

一. 基本概念:

  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:分解质因数

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容