首页 > 代码库 > 【最大公因数,最小公倍数,因式分解】
【最大公因数,最小公倍数,因式分解】
/*最大公因数,最小公倍数 by c说明:最大公因数使用辗转相除法来求,最小公倍数则由这个公式来求: GCD * LCM = 两数乘积解法:最大公因数可以使用递回与非递回求解,因式分解基本上就是使用小于输入数的数值当作除数,去除以输入数值,如果可以整除就视为因数,要比较快的解法就是求出小于该数的所有质数,并试试看是不是可以整除,求质数的问题是另一个课题,请参考 Eratosthenes 筛选求质数。*/#include <stdio.h>#include <stdlib.h>int main(void){ int m, n, r; int s; while(1){ printf("输入两数:"); scanf("%d%d", &m, &n); s = m * n; while(n != 0) { r = m % n; m = n; n = r; } printf("GCD: %d\n", m); printf("LCM: %d\n\n", s / m); } return 0;}
结果:
/*因式分解说明:最大公因数使用辗转相除法来求,最小公倍数则由这个公式来求: GCD * LCM = 两数乘积解法:最大公因数可以使用递回与非递回求解,因式分解基本上就是使用小于输入数的数值当作除数,去除以输入数值,如果可以整除就视为因数,要比较快的解法就是求出小于该数的所有质数,并试试看是不是可以整除,求质数的问题是另一个课题,请参考 Eratosthenes 筛选求质数。 */ #include <stdio.h>#include <stdlib.h>int main(void){ int i, n; printf("不用质数表\n"); while(1) { printf("请输入正整数:"); scanf("%d", &n); printf("%d = ", n); for(i = 2; i * i <= n; ) { if(n % i == 0) { printf("%d * ", i); n /= i; } else { i++; } } printf("%d\n", n); } return 0;}
结果:
/*因式分解*/ #include <stdio.h>#include <stdlib.h>#define N 1000int prime(int*); // 求质数表void factor(int*, int); // 求factorint main(void) { int ptable[N+1] = {0}; int count, i, temp; printf("用质数表\n"); while(1){ count = prime(ptable); printf("请输入正整数:"); scanf("%d", &temp); factor(ptable,temp); printf("\n"); } return 0;}int prime(int* pNum){ int i, j; int prime[N+1]; for(i = 2; i <= N;i++) prime[i] = 1; for(i = 2; i*i <= N;i++) { if(prime[i] == 1) { for(j = 2*i; j <= N;j++) { if(j % i == 0) prime[j] = 0; } } } for(i = 2, j = 0; i < N;i++) { if(prime[i] == 1) pNum[j++] = i; } return j;}void factor(int* table,int num) { int i; for(i = 0; table[i] * table[i] <= num;) { if(num % table[i] == 0) { printf("%d * ", table[i]); num /= table[i]; } else i++; } printf("%d\n", num);}
结果:
【最大公因数,最小公倍数,因式分解】
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。