📄 perfectnumber.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>
如果有一数n，其真因数（Proper factor）的总和等于n，则称之为完美数（Perfect Number），例如以下几个数都是完美数：<br>
<div style="margin-left: 40px; font-weight: bold;"><span style="font-family: Courier New,Courier,monospace;">6 = 1 + 2 + 3</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
28 = 1 + 2 + 4 + 7 + 14</span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">
496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248</span><br>
</div>
<br>
程式基本上不难，第一眼看到时会想到使用回圈求出所有真因数，再进一步求因数和，不过若n值很大，则此法会花费许多时间在回圈测试上，十分没有效率，例如求小于10000的所有完美数。<br>
<h2>解法</h2>
如何求小于10000的所有完美数？并将程式写的有效率？基本上有三个步骤：<br>
<ol>
<li>求出一定数目的质数表</li>
<li>利用质数表求指定数的因式分解</li>
<li>利用因式分解求所有真因数和，并检查是否为完美数</li>
</ol>
<br>
<a href="EratosthenesPrime.htm">步骤一</a> 与 <a href="GCDPNumber.htm">步骤二</a> 在之前讨论过了，问题在步骤三，如何求真因数和？方法很简单，要先知道将所有真因数和加上该数本身，会等于该数的两倍，例如：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">2 * 28 = 1 + 2 + 4 + 7 + 14 + 28</span><br>
</div>
<br>
等式后面可以化为：<br>
<div style="margin-left: 40px;"><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">2 * 28 = (2</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">0</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> + 2</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">1</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> + 2</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">2</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">) * (7</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">0</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;"> + 7</span><sup style="font-weight: bold; font-family: Courier New,Courier,monospace;">1</sup><span style="font-weight: bold; font-family: Courier New,Courier,monospace;">)</span><br>
</div>
<br>
所以只要求出因式分解，就可以利用回圈求得等式后面的值，将该值除以2就是真因数和了；等式后面第一眼看时可能想到使用等比级数公式来解，不过会使用到次方运算，可以在回圈走访因式分解阵列时，同时计算出等式后面的值，这在下面的实作中可以看到。 <br>
<br>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h> <br>#include <stdlib.h> <br><br>#define N 1000 <br>#define P 10000 <br><br>int prime(int*); // 求质数表 <br>int factor(int*, int, int*); // 求factor <br>int fsum(int*, int); // sum ot proper factor <br><br>int main(void) { <br> int ptable[N+1] = {0}; // 储存质数表 <br> int fact[N+1] = {0}; // 储存因式分解结果 <br> int count1, count2, i; <br><br> count1 = prime(ptable); <br><br> for(i = 0; i <= P; i++) { <br> count2 = factor(ptable, i, fact); <br> if(i == fsum(fact, count2)) <br> printf("Perfect Number: %d\n", i); <br> } <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>int factor(int* table, int num, int* frecord) { <br> int i, k; <br><br> for(i = 0, k = 0; table[i] * table[i] <= num;) { <br> if(num % table[i] == 0) { <br> frecord[k] = table[i]; <br> k++; <br> num /= table[i]; <br> } <br> else <br> i++; <br> } <br><br> frecord[k] = num; <br><br> return k+1; <br>} <br><br>int fsum(int* farr, int c) { <br> int i, r, s, q; <br><br> i = 0; <br> r = 1; <br> s = 1; <br> q = 1; <br><br> while(i < c) { <br> do { <br> r *= farr[i]; <br> q += r; <br> i++; <br> } while(i < c-1 && farr[i-1] == farr[i]); <br> s *= q; <br> r = 1; <br> q = 1; <br> } <br><br> return s / 2; <br>} <br></pre>
<br>
<ul>
<li> Java
</li>
</ul>
<pre>import java.util.ArrayList;<br><br>public class PerfectNumber {<br> public static int[] lessThan(int number) {<br> int[] primes = Prime.findPrimes(number);<br><br> ArrayList list = new ArrayList();<br> <br> for(int i = 1; i <= number; i++) { <br> int[] factors = factor(primes, i); <br> if(i == fsum(factors)) <br> list.add(new Integer(i));<br> } <br><br> int[] p = new int[list.size()];<br> Object[] objs = list.toArray(); <br> for(int i = 0; i < p.length; i++) {<br> p[i] = ((Integer) objs[i]).intValue();<br> }<br> <br> return p;<br> }<br> <br> private static int[] factor(int[] primes, int number) { <br> int[] frecord = new int[number];<br> int k = 0;<br> <br> for(int i = 0; Math.pow(primes[i], 2) <= number;) { <br> if(number % primes[i] == 0) { <br> frecord[k] = primes[i]; <br> k++; <br> number /= primes[i]; <br> } <br> else <br> i++; <br> } <br><br> frecord[k] = number; <br><br> return frecord; <br> } <br><br> private static int fsum(int[] farr) { <br> int i, r, s, q; <br><br> i = 0; <br> r = 1; <br> s = 1; <br> q = 1; <br><br> while(i < farr.length) { <br> do { <br> r *= farr[i]; <br> q += r; <br> i++; <br> } while(i < farr.length - 1 &&<br> farr[i-1] == farr[i]); <br> s *= q; <br> r = 1; <br> q = 1; <br> } <br><br> return s / 2; <br> }<br> <br> public static void main(String[] args) {<br> int[] pn = PerfectNumber.lessThan(1000);<br> <br> for(int i = 0; i < pn.length; i++) {<br> System.out.print(pn[i] + " ");<br> }<br> <br> System.out.println();<br> }<br>}</pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -