最大公因數、最小公倍數、因式分解

    最大公因數使用輾轉相除法來求，最小公倍數則由這個公式來求。

    最大公因數*最小公倍數=兩數乘積

    解法最大公因數可以使用遞歸與非遞歸求解，因式分解基本就是使用小于輸入數的數值當作除數，去除以輸入數值，如果可以整除就視為因數，要比較快的解法就是求出小于該數的所有質數，并試試看是不是可以整除，求質數是另一個問題，請參考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("最大公倍數：%d\n",m);

        printf("最小公約數：%d\n",s/m);

        return 0;

    }

    二、因式分解

    void Resolve(int n)

    {

        int i;

        printf("%d=",n);

        for(i=2;i*i<=n;)

            if(n%i==0)

            {

                printf("%d*",i);

                n/=i;

            }

            else

                i++;