HJ108 求最小公倍数
提示:文章
文章目录
- 前言
- 一、背景
- 二、
- 2.1 代码编写
- 第一版代码
- 第二版代码
- 2.2 问题探究
- 2.3 优秀代码
- 三、
- 3.1
- 总结
前言
前期疑问:
本文目标:
一、背景
最近
二、
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
总结
未完待续