C语言用筛选法求最两个数的小公倍数
时间: 2023-05-30 20:02:46 浏览: 74
以下是C语言的代码,使用筛选法求最两个数的小公倍数:
```c
#include <stdio.h>
int main() {
int a, b, max, lcm;
printf("请输入两个正整数:");
scanf("%d%d", &a, &b);
// 找出a和b的最大值
max = a > b ? a : b;
// 筛选法求最小公倍数
while (1) {
if (max % a == 0 && max % b == 0) {
lcm = max;
break;
}
max++;
}
printf("%d和%d的最小公倍数为%d", a, b, lcm);
return 0;
}
```
首先输入两个正整数,然后找出它们中的最大值,将最大值作为起始值,从起始值开始不断加1,直到找到能同时被a和b整除的数,此时找到了最小公倍数。最后输出a、b和它们的最小公倍数。
相关问题
C语言用列举法求两个数的最先公倍数
以下是使用列举法求两个数的最小公倍数的C语言代码示例:
```
#include <stdio.h>
int main() {
int num1, num2, lcm;
printf("请输入两个正整数: ");
scanf("%d %d", &num1, &num2);
lcm = (num1 > num2) ? num1 : num2;
while (1) {
if (lcm % num1 == 0 && lcm % num2 == 0) {
printf("最小公倍数为 %d", lcm);
break;
}
lcm++;
}
return 0;
}
```
运行示例:
请输入两个正整数: 12 18
最小公倍数为 36
说明:该程序通过一个while循环,不断增加一个变量lcm的值,判断是否同时能被两个输入的数整除,如果可以则说明找到了最小公倍数。
C语言用筛选法求最小公倍数
以下是用筛选法求最小公倍数的C语言代码:
```c
#include <stdio.h>
int main() {
int n, i, j, k, lcm;
printf("请输入一个正整数n:\n");
scanf("%d", &n);
int primes[n + 1];
for (i = 2; i <= n; i++) {
primes[i] = 1; // 初始化为素数
}
for (i = 2; i <= n; i++) {
if (primes[i]) {
// 将i的倍数标记为非素数
for (j = i * i; j <= n; j += i) {
primes[j] = 0;
}
// 计算i的最高次幂
k = i;
while (k * i <= n) {
k *= i;
}
// 更新最小公倍数
lcm *= k;
}
}
printf("1到%d的最小公倍数为%d\n", n, lcm);
return 0;
}
```
该程序使用了一个数组`primes`来记录每个数是否为素数,初始化时都为素数。然后从2开始遍历到n,对于每个素数i,将其所有倍数标记为非素数,并计算i的最高次幂k。最后将所有i的最高次幂相乘,得到最小公倍数lcm。最终输出1到n的最小公倍数。