最大公因數使用輾轉相除法來求,最小公倍數則由這個公式來求:
GCD * LCM = 兩數乘積
解法最大公因數可以使用遞回與非遞回求解,因式分解基本上就是使用小于輸入數的數值當作除數,去除以輸入數值,如果可以整除就視為因數,要比較快的解法就是求出小于該數的所有質數,并試試看是不是可以整除,求質數的問題是另一個課題,請參考 Eratosthenes 篩選求質數。
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int m, n, r;
int s;
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", s/m);
return 0;
}
實作(因式分解)
C(不用質數表)
#include <stdio.h>
#include <stdlib.h>
int main(void) {
int i, n;
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;
}
C(使用質數表)
#include <stdio.h>
#include <stdlib.h>
#define N 1000
int prime(int*); // 求質數表
void factor(int*, int); // 求factor
int main(void) {
int ptable[N+1] = {0};
int count, i, temp;
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);
}