一. 基本概念：
如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示两个整数的关系，不能单独存在。
几个整数中公有的约束，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。数学公式记为(12,16) = 4"倍"与"倍数"是不同的概念，"倍"表示两个数相除的商，他可以是整数、小数或者分数。"倍数"只是在数的
整除的范围内，相对于"约数"而言的一个概念，表示的是能被某一个自然数整除的数。 几个自然数公有的倍数，叫做这几个数的公倍数，其中最小的一个自然数，叫做这几个数的最小公倍数[12,15,18]=180. 若干个互质数的最小公倍数为他们的乘积质数：又称
素数.一个大于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];
}
