📄 gcdpnumber.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>最大公因数、最小公倍数、因式分解</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 最大公因数、最小公倍数、因式分解</a></h1>
<h2>说明</h2>
最大公因数使用辗转相除法来求，最小公倍数则由这个公式来求：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold;">GCD * LCM = 两数乘积</span><br>
</div>
<h2>解法</h2>
最大公因数可以使用递回与非递回求解，因式分解基本上就是使用小于输入数的数值当作除数，去除以输入数值，如果可以整除就视为因数，要比较快的解法就是求出小于该数的所有质数，并试试看是不是可以整除，求质数的问题是另一个课题，请参考 <a href="EratosthenesPrime.htm">Eratosthenes 筛选求质数</a>。<br>
<br>
<h2> 实作（最大公因数、最小公倍数）</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>int main(void) { <br> int m, n, r; <br> int s;<br><br> printf("输入两数："); <br> scanf("%d %d", &m, &n); <br> s = m * n;<br><br> while(n != 0) { <br> r = m % n; <br> m = n; <br> n = r; <br> } <br><br> printf("GCD：%d\n", m); <br> printf("LCM：%d\n", s/m); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>public class GcdLcm {<br> public static int gcdOf(int m, int n) {<br> int r;<br> <br> while(n != 0) { <br> r = m % n; <br> m = n; <br> n = r; <br> }<br> <br> return m;<br> }<br> <br> public static int lcmOf(int m, int n) {<br> return m * n / gcdOf(m, n);<br> }<br> <br> public static void main(String[] args) {<br> System.out.println("GCD of (10, 4) = " + <br> GcdLcm.gcdOf(10, 4));<br> System.out.println("LCM of (10, 4) = " + <br> GcdLcm.lcmOf(10, 4));<br> }<br>} <br></pre>
<h2> 实作（因式分解）</h2>
<ul>
<li> C（不用质数表）
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>int main(void) { <br> int i, n; <br><br> printf("请输入整数："); <br> scanf("%d", &n); <br> printf("%d = ", n); <br><br> for(i = 2; i * i <= n;) { <br> if(n % i == 0) { <br> printf("%d * ", i); <br> n /= i; <br> } <br> else <br> i++; <br> } <br><br> printf("%d\n", n); <br><br> return 0; <br>} <br></pre>
<br>
<ul>
<li> C（使用质数表）
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>#define N 1000 <br><br>int prime(int*); // 求质数表 <br>void factor(int*, int); // 求factor <br><br>int main(void) { <br> int ptable[N+1] = {0}; <br> int count, i, temp; <br><br> count = prime(ptable); <br><br> printf("请输入一数："); <br> scanf("%d", &temp); <br> factor(ptable, temp); <br><br> printf("\n"); <br><br> return 0; <br> } <br><br> int prime(int* pNum) { <br> int i, j; <br> int prime[N+1]; <br><br> for(i = 2; i <= N; i++) <br> prime[i] = 1; <br><br> for(i = 2; i*i <= N; i++) { <br> if(prime[i] == 1) { <br> for(j = 2*i; j <= N; j++) { <br> if(j % i == 0) <br> prime[j] = 0; <br> } <br> } <br> } <br><br> for(i = 2, j = 0; i < N; i++) { <br> if(prime[i] == 1) <br> pNum[j++] = i; <br> } <br><br> return j; <br>} <br><br>void factor(int* table, int num) { <br> int i; <br><br> for(i = 0; table[i] * table[i] <= num;) { <br> if(num % table[i] == 0) { <br> printf("%d * ", table[i]); <br> num /= table[i]; <br> } <br> else <br> i++; <br> } <br><br> printf("%d\n", num); <br>}<br> <br></pre>
<br>
<ul>
<li> Java（使用质数表）
</li>
</ul>
<pre>import java.util.ArrayList;<br><br>public class Factor {<br> public static int[] factor(int num) {<br> int[] pNum = Prime.findPrimes(num);<br> <br> ArrayList list = new ArrayList();<br> <br> for(int i = 0; pNum[i] * pNum[i] <= num;) { <br> if(num % pNum[i] == 0) { <br> list.add(new Integer(pNum[i]));<br> num /= pNum[i]; <br> } <br> else <br> i++; <br> } <br><br> list.add(new Integer(num));<br> <br> int[] f = new int[list.size()];<br> Object[] objs = list.toArray();<br> for(int i = 0; i < f.length; i++) {<br> f[i] = ((Integer) objs[i]).intValue();<br> }<br> <br> return f;<br> }<br> <br> public static void main(String[] args) {<br> int[] f = Factor.factor(100);<br> for(int i = 0; i < f.length; i++) {<br> System.out.print(f[i] + " ");<br> }<br> System.out.println();<br> }<br>}</pre>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -