跳至主要内容

求完美数

求完美数

redraiment, 2008-07-10





　　一个数如果恰好等于它的因子之和，这个数就称为“完美数”或“完数”，例如 6=1+2+3（6的因子是1,2,3）。完美数的一些性质：
    1. 欧几里德证明了：一个偶数是完数，当且仅当它具有如下形式：2(p-1)×(2p-1) 其中 p 和 2p-1 是素数。尽管没有发现奇完数，但是当代数学家奥斯丁·欧尔（Oystein Ore）证明，若有奇完全数，则其形状必然是 12p+1 或 36p+9 的形式，其中 p 是素数。在 1018 以下的自然数中奇完数是不存在的。
    2. 除 6 以外的偶完数，把它的各位数字相加，直到变成一位数，那么这个一位数一定是 1（亦即：除6以外的完数，被9除都余1） 28：2+8=10，1+0=1 496：4+9+6=19，1+9=10，1+0=1
    3. 因为 2p 是 2 的幂，用C语言也就是 1 << p，那么 2p-1 的二进制也就是 p 个 1 组成了，而 2(p-1) 是 2的幂，这两个数相乘，也就相当于把 2p-1 向左移 p-1 位，即 (2p-1) << (p-1)，那所有完美数的二进制就是前面 p 个 1，后面跟着 p-1 个 0。 所以偶完数都可以表达为 2 的一些连续正整数次幂之和，如：
      6 = 21 + 22; 28 = 22 + 23 + 24; 8128 = 26 + 27 + ... + 212; 33550336 = 212 + 213 + ... + 224
      j = ((1 + (i ^ (i-1) )) >> 1) + i - 1;
      (j & (j + 1)) || (i & 1)
    4. 上面的代码可以判断整数 i 是否是前面 1 后面 0 的形式。
    5. 每一个偶完数都可以写成连续自然数之和： 6=1+2+3; 28=1+2+3+4+5+6+7; 496=1+2+3+…+30+31
    6. 除6以外的偶完数，还可以表示成连续奇数的立方和（被加的项共有)： 28 = 13 + 33; 496 = 13 + 33 + 53 + 73; 8128 = 13 + 33 + 53 + ... + 153; 33550336 = 13 + 33 + 53 + ... + 1253 + 1273
    7. 每一个完数的所有约数(包括本身)的倒数之和，都等于2： 1/1 + 1/2 + 1/3 + 1/6 = 2; 1/1 + 1/2 + 1/4 + 1/7 + 1/14 + 1/28 = 2
　　了解了上面一些性质后，就可以简单的来写一个求完美数的程序了。
#include <stdio.h>

#ifndef WIN32
typedef long long ll;
#else
typedef __int64 ll;
#endif

int main(void)
{
    ll i, j, n, x;

    for (n = 2; n <= 31; n++)
    {
        x = (1 << n) - 1;
        for(i = 3; i*i <= x; i += 2)
            if(x % i == 0)
                break;
        if(i*i <= x) continue;
        printf("%lld\n", (1 << (n - 1)) * x);
    }

    return 0;
}

　　运行结果：
6
28
496
8128
33550336
8589869056
137438691328
2305843008139952128
　　到目前为止，已经求出的2p-1是素数的有25个：2、3、5、7、13、17、19、31、61、89、107、127、521、607、1279、2203、2281、3217、4253、4423、9689、9941、11213、19937、21701。 据说最后一个即221701－1是1978年两名美国大学生新发现的截止目前为止最大的一个素数，所以我们可以利用这个结果来求已知的完美数：
import java.math.BigInteger;

public class Main
{
    public static void main(String[] argv)
    {
        int [] prime = {
            2,3,5,7,13,17,19,31,61,89,107,127,
            521,607,1279,2203,2281,3217,4253,
            4423,9689,9941,11213,19937,21701
        };
        BigInteger x = BigInteger.ONE;
        for (int i = 0; i < prime.length; i++)
            System.out.println ( x.shiftLeft(prime[i]-1)
                .multiply(x.shiftLeft(prime[i])
                .subtract(x)));
    }
}
　　最后一个完美数的长度是13066！堪称是BinIntegest了



标签：

评论

发表评论

此博客中的热门博文

JavaScript中的字符串乘法

JavaScript中的字符串乘法 redraiment, Date 原文 原文地址： http://www.davidflanagan.com/2009/08/string-multipli.html 原作者：David Flanagan In Ruby, the "*" operator used with a string on the left and a number on the right does string repetition. "Ruby"*2 evaluates to "RubyRuby", for example. This is only occasionally useful (when creating lines of hyphens for ASCII tables, for example) but it seems kind of neat. And it sure beats having to write a loop and concatenate n copies of a string one at a time--that just seems really inefficient. I just realized that there is a clever way to implement string multiplication in JavaScript: String.prototype.times = function(n) {     return Array.prototype.join.call({length:n+1}, this); }; "js".times(5) // => "jsjsjsjsjs" This method takes advantage of the behavior of the  Array.join()  method for arrays that have undefined elements. But it doesn't even bother creating an array with n+1 undefined ele...
发表评论
阅读全文

DAO层测试

<dependency> <groupId>com.wix</groupId> <artifactId>wix-embedded-mysql</artifactId> <version>2.1.4</version> <scope>test</scope> </dependency> 利用 wix-embedded-mysql 把MySQL嵌入到进程中，作为内存型的MySQL来做单元测试。 脚本： resources/migrations/mysql/<database>/<timestamp>_<action>.sql 但多个项目需要共享数据库脚本，可能可以用 git submodule 共享。
发表评论
阅读全文

人所不欲，勿施于人

谁说博客也要像论文一样结构清晰、有条理？！ 软件卸载 昨天整理自己的本本，卸载了 VMware 7.0 + 深度XP，MS Office 2007 以及 Visual Basic 6.0。我承认这些都是盗版软件，不过剩下的应用程序都是自由软件（freeware）或免费软件（freeware），这下我的计算机“干净”了。闲来无事，我就细数了一下当初装这些软件的原因： VMware + XP：当初刚买本本的时候，正好在上软件工程实践，紧遵老师的教导“将自己的开发环境随身携带”，自然第一款软件就是装了虚拟机（学校机房里是肆无忌惮地用盗版 VMware），另外上课指定使用 Visio 作图，那也只好一起装了；当然，也有部分原因是因为某些人的计算机装的是 XP，我这边有个 XP 环境也是为了方便问题重现（我的本本预装了 Vista）。 MS Office 2007：在毕设期间，我也还是用 Open Office 和 WPS 2010，但现在公司用的却是 Office 2007（正版）。我这次卸载这款办公软件其实也是在提醒自己：工作的事情要在工作时间里完成！ VB 6：你可能无法想象在我们科班的毕业设计中有多少是 VB6 项目，从大二开始，每逢毕业将至，总会有人来找我帮忙看那些不晓得从哪儿搜罗来的 VB6 代码，经不住软磨硬泡，我总会帮着改改；另一个原因在我自己，我一直下不了决心去学 MFC 等，所以但凡要做 GUI 程序，我都是拿 VB6 来画界面，再调用由 C 语言开发的 DLL 库，不过现在改用 QT，于是 VB6 可以功成身退了。 己所不欲，勿施于人 有些人就喜欢把自己的事全盘交托给别人来做，我一直不明白他们既然有精力去说服别人，为什么就没耐心自己去完成（所以我下面说人和人之间是无法理解的）。既然自己都认为这是无聊的事情，为什么偏偏又假设其他人会愿意无偿地帮你来完成呢？ 两千多年前，孔老夫子提出“己所不欲，勿施于人”的观点，但到了今天，我听到关于这句话时的语境普遍是，A说：“那个XX东西你也不要了（或要了也没用），不如就让给我吧？”，B就义正言辞地反对：“那怎么可以！己所不欲，勿施于人嘛。” 己所甚欲，勿施于人 易中天老师在《百家讲坛》讲解诸子百家...
发表评论
阅读全文