最大公约数和最小公倍数

一. 基本概念：

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