最大公约数和最小公倍数

求（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。

#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

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

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

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

#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];
    }
}

把每个数`分别`分解质因数，再把各数中`全部` `公有`质因数相乘，所得的积 就是这几个数的最大公约数

#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];
    }