HJ108 求最小公倍数

提示：文章

前言

前期疑问：
本文目标：

---

一、背景

最近

二、

2.1 代码编写

第一版代码

#include "securec.h"int main()
{int num1 = 0, num2 = 2;int array1[100000] = {0};int array2[100000] = {0};printf("FindCommonMutiple\n");scanf("%d %d", &num1, &num2);int minNum = 0;int maxNum = 0;if (num1 < num2) {minNum = num1;maxNum = num2;} else {minNum = num2;maxNum = num1;}int maxHash = 0;int minNumTemp = minNum;int index1 = 0;for (int i = 1; i <= minNumTemp; i++) {if (minNumTemp % i == 0) {array1[index1++] = i;maxHash = i > maxHash ? i : maxHash;}}int maxNumTemp = maxNum;int index2 = 0;for (int i = 1; i <= maxNumTemp; i++) {if (maxNumTemp % i == 0) {array2[index2++] = i;maxHash = i > maxHash ? i : maxHash;}}int index = index1 > index2 ? index1 : index2;int* array = (int*) malloc(sizeof(int) * maxHash);memset(array, 0, sizeof(int) * maxHash);for (int i = 0; i < index; i++) {if (array1[i] != 0) {array[array1[i]] += 1;}if (array2[i] != 0) {array[array2[i]] += 1;}}int commonNum = 0;for (int i = index; i > 0; i--) {if (array[i] == 2) {commonNum = i;break;}}int commonMultiple = num1 / commonNum * num2 / commonNum * commonNum;printf("%d", commonMultiple);return 0;
}

可以通过输入为【5 7】和输入为【4 6】的示例

对于示例为 【6 6】的示例没有通过。

下面调试一下代码

第二版代码

#include <stdio.h>int main() {int num1 = 0, num2 = 2;int array1[100000] = {0};int array2[100000] = {0};scanf("%d %d", &num1, &num2);int minNum = 0;int maxNum = 0;if (num1 < num2) {minNum = num1;maxNum = num2;} else {minNum = num2;maxNum = num1;}int maxHash = 0;int minNumTemp = minNum;int index1 = 0;for (int i = 1; i <= minNumTemp; i++) {if (minNumTemp % i == 0) {array1[index1++] = i;maxHash = i > maxHash ? i : maxHash;}}int maxNumTemp = maxNum;int index2 = 0;for (int i = 1; i <= maxNumTemp; i++) {if (maxNumTemp % i == 0) {array2[index2++] = i;maxHash = i > maxHash ? i : maxHash;}}int index = index1 > index2 ? index1 : index2;int *array = (int*)malloc(sizeof(int) * (maxHash + 1));memset(array, 0, sizeof(int) * (maxHash + 1));for (int i = 0; i < index; i++) {if (array1[i] != 0) {array[array1[i]] += 1;}if (array2[i] != 0) {array[array2[i]] += 1;}}int commonNum = 0;for (int i = maxHash; i > 0; i--) {if (array[i] == 2) {commonNum = i;break;}}int commonMultiple = num1 / commonNum * num2 / commonNum * commonNum;printf("%d", commonMultiple);free(array);return 0;
}

改成这样可以通过全部代码

2.2 问题探究

上述代码思路就是找到最大公约数，然后用两个数除以公约数，两个商和最大公约数相乘就是两个数的最大公倍数。

但是我不知道怎么求公约数。搜了百度才知道。

实际上上述代码包含了怎么求约数，怎么求公约数，怎么求公倍数。都有了

最后还要记得释放堆内存：free(array);

2.3 优秀代码

参考别人的代码如下

#include<stdio.h>
int main(){int commonmax=1;int a,b;scanf("%d %d",&a,&b);for(int i=1;i<=(a>b?b:a);i++){if(a%i==0 && b%i==0 && i>commonmax)commonmax=i;}printf("%d",a*b/commonmax);return 0;
}

别人的代码简洁很多，看了下代码，基本逻辑也是先找到最大公约数，然后计算出最小公倍数。

三、

3.1

---

总结

未完待续