解法思路
回Algorithm
說明可整除兩數的稱之為公因數，可使用輾轉相除法來求最大公因數，可被兩數整除的某數稱之為公倍數，兩數的最大公因數乘最小公倍數正好等於兩數乘積。
因數分解就是求某數的所有因數。
解法因數分解就是使用小於輸入數的數值當作除數，去除以輸入數值，如果可以整除就視為因數。
例如：C（不用質數表的因數分解）
#include#includeintmain(void){intn;printf("請輸入整數：");scanf("%d",&n);printf("%d=",n);inti;for(i=2;i*i<=n;)if(n%i==0){printf("%d*",i);n/=i;}else{i++;}return0;}
要比較快的解法就是求出小於該數的所有質數，並試試看是不是可以整除，求質數的問題是另一個課題，請參考Eratosthenes篩選求質數。
最大公因數、最小公倍數：C Java Python Scala Ruby JavaScript Haskell
使用質數表因數分解：C Java Python Scala Ruby JavaScript Haskell
C
#include#includeintgcd(intm,intn){while(n!=0){intr=m%n;m=n;n=r;}returnm;}intlcm(intm,intn){returnm*n/gcd(m,n);}intmain(void){intm,n;printf("輸入兩數：");scanf("%d%d",&m,&n);printf("Gcd：%d\n",gcd(m,n));printf("Lcm：%d\n",lcm(m,n));return0;}
Java
publicclassMain{publicstaticintgcd(intm,intn){returnn==0?m:gcd(n,m%n);}publicstaticintlcm(intm,intn){returnm*n/gcd(m,n);}publicstaticvoidmain(String[]args){System.out.printf("GCDof(10,4)=%d",gcd(10,4));System.out.printf("LCMof(10,4)=%d",lcm(10,4));}}Pythondefgcd(m,n):returnmifn==0elsegcd(n,m%n)deflcm(m,n):returnm*n//gcd(m,n)m=int(input("輸入m："))n=int(input("輸入n："))print("Gcd:",gcd(m,n))print("Lcm:",lcm(m,n))Scaladefgcd(m:Int,n:Int):Int=if(n==0)melsegcd(n,m%n)deflcm(m:Int,n:Int)=m*n/gcd(m,n)println("Gcdof(10,4)=%d".format(gcd(10,4)))println("Lcmof(10,4)=%d".format(lcm(10,4)))
Ruby
#encoding:Big5defgcd(m,n)ifn==0;melsegcd(n,m%n)endenddeflcm(m,n)m*n/gcd(m,n)endprint"輸入m："m=gets.to_iprint"輸入n："n=gets.to_iprint"Gcd:",gcd(m,n),"\n"print"Lcm:",lcm(m,n),"\n"
JavaScript
functiongcd(m,n){returnn===0?m:gcd(n,m%n);}functionlcm(m,n){returnm*n/gcd(m,n);}print('GCDof(10,4)='+gcd(10,4));print('LCMof(10,4)='+lcm(10,4));
Haskell
gcd'mn=ifn==0thenmelsegcdn(m`mod`n)lcm'mn=m*n`div`(gcdmn)main=doputStrLn("Gcdof(10,4)="++(show\$gcd'104))putStrLn("Lcmof(10,4)="++(show\$lcm'104))
C
#include#include#defineN1000voidcreate(int*);//建立質數表voidfilter(int*,int);voidfactor(int,int*,int*);//因數分解intmain(void){intprimes[N+1]={0};create(primes);printf("請輸入一數：");intnum;scanf("%d",&num);intfactors[N/2+1]={0};factor(num,factors,primes);inti;for(i=0;factors[i]!=0;i++){printf("%d",factors[i]);}return0;}voidcreate(int*primes){primes[2]=primes[3]=primes[5]=1;inti;for(i=1;6*i+5<=N;i++){primes[6*i+1]=primes[6*i+5]=1;}if(6*i+1<=N){primes[6*i+1]=1;}intn;for(n=0;(6*n+5)*(6*n+5)<=N;n++){filter(primes,6*n+1);filter(primes,6*n+5);}if((6*n+1)*(6*n+1)<=N){filter(primes,6*n+1);}}voidfilter(int*primes,inti){if(primes[i]){intj;for(j=2;j*i<=N;j++){primes[j*i]=0;}}}voidfactor(intnum,int*factors,int*primes){inti,j;for(i=2,j=0;i*i<=num;)if(primes[i]&&num%i==0){factors[j++]=i;num/=i;}else{i++;}factors[j]=num;}
Java
//使用Eratosthenes篩選求質數中的Primeimportjava.util.*;publicclassFactor{publicstaticListfactor(intn){Listprimes=Prime.create(n/2);returnfactor(n,primes);}publicstaticListfactor(intn,Listprimes){Listfactors=newArrayList<>();for(inti=0;primes.get(i)<=Math.sqrt(n);){if(n%primes.get(i)==0){factors.add(primes.get(i));n/=primes.get(i);}else{i++;}}factors.add(n);returnfactors;}publicstaticvoidmain(String[]args){for(Integerf:factor(100)){System.out.printf("%d",f);}}}Python#使用Eratosthenes篩選求質數中的createdeffactor(n):defft(ps,num):ifps[0]**2>num:return[num]else:return(ps[0:1]+ft(ps,num//ps[0])ifnum%ps[0]==0elseft(ps[1:],num))returnft(create(n//2),n)print(factor(100))Scala//使用Eratosthenes篩選求質數中的createdeffactor(n:Int)={defft(ps:List[Int],num:Int):List[Int]={if(math.pow(ps.head,2)>num)List(num)elseif(num%ps.head==0)ps.head::ft(ps,num/ps.head)elseft(ps.tail,num)}ft(create(n/2),n)}print(factor(100))
Ruby
#使用Eratosthenes篩選求質數中的createdeffactor(n)ft=->(ps,num){ifps[0]**2>num[num]elseifnum%ps[0]==0ps[0,1]+ft.call(ps,num/ps[0])elseft.call(ps[1,ps.size],num)endend}ft.call(create(n/2),n)endprint(factor(100))
JavaScript
//使用Eratosthenes篩選求質數中的createfunctionfactor(n){varprimes=create(parseInt(n/2));varfactors=[];for(vari=0;primes[i]<=Math.sqrt(n);){if(n%primes[i]===0){factors.push(primes[i]);n/=primes[i];}else{i++;}}factors.push(n);returnfactors;}print(factor(100));
Haskell
{-使用Eratosthenes篩選求質數中的create-}factorn=ft(create(n`div`2))nwhereftpsnum=if(headps)^2>numthen[num]elseifnum`mod`(headps)==0then(headps):ftps(num`div`(headps))elseft(tailps)nummain=print\$factor100
